洛谷 P4886 快递员树的重心

文章目录

洛谷 P4886 快递员

洛谷 P4886 快递员

题意

在一个树上有m对点 $(u_{i}, v_{i}) ，$ 我们在这个树上选择一个点root 使得 $d i s t a n c e (r o o t, v_{i}) + d i s t a n c e (r o o t, u_{i})$ 的最大值最小

分析

类似于点分治，我们选择随意选择一个点作为所求的点，求出它与m对点的最长距离，并求出q个最长距离的点对，对于这q个点对，
有三种情况

如果其中有一个点对在这个点的不同子树上，那么最长距离已经不可能减少，这个时候 $d i s t a n c e (r o o t, v_{i}) + d i s t a n c e (r o o t, u_{i}) = d i s t a n c e (v_{i}, u_{i})$
如果有两个点对在不同的子树上，那么最长距离同样不可能减少了
如果所有的最长点对都在一个子树上，那么最优解可能在这个字数上，可能并非一定，因为在这个子树上选点可能导致其它本来不是最长距离的变成了最长距离

其中我们在子树上选择重心作为子树的根，递归求解取最小值即可

参考代码

 #include <bits/stdc++.h> #define mem(ar,num) memset(ar,num,sizeof(ar)) #define me(ar) memset(ar,0,sizeof(ar)) #define lowbit(x) (x&(-x)) #define Pb push_back #define FI first #define SE second #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define IOS ios::sync_with_stdio(false) #define DEBUG cout<<endl<<"DEBUG"<<endl;  using namespace std; typedef long long LL; typedef unsigned long long ULL; const int prime = 999983; const int INF = 0x7FFFFFFF; const LL INFF =0x7FFFFFFFFFFFFFFF; const double pi = acos(-1.0); const double inf = 1e18; const double eps = 1e-6; const LL mod = 1e9 + 7; LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;} LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;} int dr[2][4] = {1,-1,0,0,0,0,-1,1}; typedef pair<int,int> P; const int maxn = 1e5+100; // 策略，如果根在x-y的路径上，已经是最优的了，如果x1-y1 在一个子树，x2-y2 在另一个子树，这也已经是最优了 // 邻接表存图 struct Edge{ int to,w,next; Edge(int v = 0,int w = 0):to(v),w(w){} }; Edge edge[maxn<<1]; int tot = 0; int head[maxn]; void init(){ memset(head,-1,sizeof(head)); tot = 0; } void addEdge(int u,int v,int w){ edge[++tot].to = v,edge[tot].w = w,edge[tot].next = head[u],head[u] = tot; } // 求重心 int dp[maxn],size[maxn]; bool vis[maxn]; void getroot(int u,int fa,int allnode,int &root){ dp[u] = 0; size[u] = 1; for(int i = head[u],v;i != -1;i = edge[i].next){ // DEBUG; v = edge[i].to; if(v == fa||vis[v]) continue; getroot(v,u,allnode,root); size[u] += size[v]; dp[u] = max(dp[u],size[v]); } dp[u] = max(dp[u],allnode-size[u]); if(dp[u] < dp[root]) root = u; } // 本题相关 int n,m; int x[maxn],y[maxn]; int dis[maxn],belong[maxn]; int ans = INF; void dfsdepth(int u,int fa,int rt){ for(int i = head[u],v;i != -1;i = edge[i].next){ v = edge[i].to; if(v == fa) continue; belong[v] = rt; dis[v] = dis[u] + edge[i].w; dfsdepth(v,u,rt); } } void solve(int u){ if(vis[u]){ printf("%d\n", ans); exit(0); } vis[u] = 1; belong[u] = u; dis[u] = 0; for(int i = head[u],v;i != -1;i = edge[i].next){ v = edge[i].to; dis[v] = edge[i].w; // belong[u] = v dfsdepth(v,u,v); } belong[u] = u; int Max = 0; for(int i = 0;i < m; ++i){ Max = max(Max,dis[x[i]]+dis[y[i]]); } ans = min(Max,ans); int now = 0; for(int i = 0;i < m; ++i){ if(dis[x[i]]+dis[y[i]] == Max){ if(belong[x[i]] != belong[y[i]]) return ; if(now == 0) now = belong[x[i]]; else if(belong[x[i]] != now) return ; } } if(ans == 0) return ; int root = 0; getroot(now,u,size[now],root); solve(root); } int main(void) { init(); scanf("%d%d",&n,&m); rep(i,1,n){ int u,v,w; scanf("%d%d%d",&u,&v,&w); assert(u!=v); addEdge(u,v,w); addEdge(v,u,w); } rep(i,0,m){ scanf("%d%d",&x[i],&y[i]); //assert(x[i] != y[i]); } if(n==1) return 0*printf("0"); ans = INF; int root = 0; dp[root] = INF; getroot(1,-1,n,root); solve(root); printf("%d\n",ans); return 0; }