龙岗个性化网站建设价格低_中铁建设集团有限公司官网_上海百度推广公司排名_推广策划方案怎么做

题目连接

最大值最小，对于套路化的题目来说一般先想二分?(不行试试DP?再试试网络流?),我们先试着二分答案$mid$，考虑如何检查,
题目说可以选择任一点为根，不好考虑我们不妨先选择1作为根节点
因为要让两个点的距离都尽可能的小,所以自然的选取两个节点的LCA会是第一直觉.
设两点间距离是$dis$ ,点x到 LCA 的距离是 $len$ ,首先显然的如果 $dis\le mid$随便选择一个点作为根都是可行的，否则,
对于x来说我们要找到它可以在mid步到达的节点(y同理) 如果$len\le mid$ 那就说明在x到LCA的路径内部就已经会走mid步,就是官方题解中的mid级子树内,否则我们找到距离y 的$dis-mid-1$节点，在这个节点到x之间，x走的步数都不超过mid.这样对于每一对点我们可以知道符合条件的节点是哪些，对这些节点取个交集即可，这里我采用了dfn序+差分求前缀和的方式

至此，我们的check策略就清楚了,对于每一个点对，求出符合条件的节点范围取交集即可,时间复杂度$O(nlog)$

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128;constexpr int maxn = 1e5+10;
int n,m,dep[maxn],fa[maxn][22],LCA[maxn],X[maxn],Y[maxn];//点，边，深度，倍增数组，LCA数组，点x,点y
int l[maxn],r[maxn],idx;//dfn序
vector<int> g[maxn];//树void dfs(int x,int father){dep[x] = dep[father]+1;fa[x][0]=father;l[x] = ++idx;for(int i = 0;i<=20;++i) fa[x][i+1] = fa[fa[x][i]][i];for(auto y:g[x]){if(y==father) continue;dfs(y,x);}r[x] = idx;
}
int lca(int x,int y){if(dep[x]<dep[y]) swap(x,y);for(int i = 20;i>=0;--i){if(dep[fa[x][i]]>=dep[y]){x = fa[x][i];}}if(x==y) return x;for(int i = 20;i>=0;--i){if(fa[x][i]!=fa[y][i]){x = fa[x][i];y = fa[y][i];}}return fa[x][0];
}int zx(int x, int k) {//求k级祖先for (int i = 0; k; ++i, k >>= 1)if (k & 1) x = fa[x][i];return x;
}void solve(){cin>>n>>m;for(int i = 1;i<=n-1;++i){int x,y;cin>>x>>y;g[x].emplace_back(y);g[y].emplace_back(x);}dfs(1,0);for(int i = 1;i<=m;++i){cin>>X[i]>>Y[i];LCA[i] = lca(X[i],Y[i]);}auto dis=[&](int x,int y,int z)->int{return dep[x]-2ll*dep[z]+dep[y];};auto check=[&](int mid)->bool{int c=0;vector<int> cnt(n+10,0);auto add = [&](int a, int b) { // 区间[a,b]加1if (a > b) return;cnt[a]++;cnt[b + 1]--;};auto exclude = [&](int a, int b) { // 补集：区间[1,a-1]和[b+1,n]加1add(1, a - 1);add(b + 1, n);};for(int i = 1;i<=m;++i){int x = X[i],y = Y[i];int dist = dep[x] + dep[y] - 2 * dep[LCA[i]];if(dist<=mid) continue;else if(dist>2*mid) return 0;else{int len = dep[x]-dep[LCA[i]];if(len>mid){int anc = zx(x,mid);add(l[anc], r[anc]);c++;}else{if(dist-mid-1<0) continue;int anc = zx(y,dist-mid-1);exclude(l[anc], r[anc]);c++;}len = dep[y]-dep[LCA[i]];if(len>mid){int anc = zx(y,mid);add(l[anc], r[anc]);c++;}else{if(dist-mid-1<0) continue;int anc = zx(x,dist-mid-1);exclude(l[anc], r[anc]);c++;}}}if(c==0) return 1;int sum = 0;for(int i = 1;i<=n;++i){sum+=cnt[i];if(sum==c) return 1;}return 0;};int l = 0,r = maxn;while(l<=r){int mid = (l+r)>>1;if(check(mid)) r = mid-1;else l = mid+1;}cout<<l<<"\n";
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int t=1;//cin>>t;while(t--) solve();return 0;
}