思路：二分 + LCA
看到这道题目的第一眼，就想到了LCA，但是维护了LCA后该如何求答案呢？这时便可以考虑二分。
我们可以先预处理所有任务所需的时间，以及起点和终点的LCA，然后二分任务需要的最大时间。
预处理时间和LCA都很简单，主要是check怎么写。
很容易可以想到如果时间大于mid的任务所走的路径都覆盖过某一条边，且这条边消失都可以让任务时间小于mid，那么这个mid肯定是合法的。
那么我们就可以预处理一个 up 数组，up i 表示节点 i 到他父亲的距离。在check的时候枚举每一个时间大于 mid 的任务，遍历一遍他的路径，在每条消失就可以使时间小于等于 mid 的边打上一个标记，如果有一条边上的标记等于时间大于 mid 的任务数，则返回 true。
1 bool check(int len) 2 { 3 if(plan[m].dist<=len)return true; 4 for(int i=1;i<=n;i++)used[i]=0; 5 int x=0,maxn=0; 6 //x是大于 mid 的任务数，在循环中统计，maxn是边上标记个数的最大值 7 for(int i=m;i>=1;i--) 8 { 9 if(plan[i].dist<=len)break; 10 x++; 11 int u=plan[i].st,v=plan[i].ed,luv=plan[i].lca,c=plan[i].dist-len; 12 while(u!=luv) 13 { 14 if(up[u]>=c) 15 { 16 used[u]++; 17 maxn=maxn<used[u]?used[u]:maxn; 18 } 19 u=f[u][0]; 20 } 21 while(v!=luv) 22 { 23 if(up[v]>=c) 24 { 25 used[v]++; 26 maxn=maxn<used[v]?used[v]:maxn; 27 } 28 v=f[v][0]; 29 }//因为时限是2s，所以只需要暴力枚举端点到LCA的每一条边就可以了 30 if(maxn<x)return false; 31 } 32 return true; 33 }
完整代码如下：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 7 const int N = 300000 + 10; 8 9 inline int read() 10 { 11 int res=0; 12 char ch=getchar(); 13 while(ch<'0'||ch>'9')ch=getchar(); 14 while(ch>='0'&&ch<='9')res=(res<<3)+(res<<1)+ch-'0',ch=getchar(); 15 return res; 16 } 17 18 struct edge{ 19 int next,to,w; 20 }r[N<<1]; 21 22 int head[N],tot; 23 24 void add(int u,int v,int w) 25 { 26 r[++tot]=(edge){head[u],v,w}; 27 head[u]=tot; 28 } 29 30 int dep[N],f[N][22],sum[N],up[N]; 31 32 void dfs(int u,int father,int deep) 33 { 34 dep[u]=deep; 35 f[u][0]=father; 36 for(int e=head[u];e;e=r[e].next) 37 { 38 int v=r[e].to; 39 if(v==father)continue; 40 sum[v]=sum[u]+r[e].w; 41 //处理从根节点（我这里将根节点设为1）到u的距离 42 up[v]=r[e].w; 43 //处理自己到父亲的距离，其实不要也可以，直接用sum求就可以 44 dfs(v,u,deep+1); 45 } 46 } 47 48 int LCA(int u,int v) 49 { 50 if(dep[u]<dep[v])swap(u,v); 51 for(int i=19;i>=0;i--) 52 if(dep[f[u][i]]>=dep[v]) 53 u=f[u][i]; 54 if(u==v)return u; 55 for(int i=19;i>=0;i--) 56 if(f[u][i]!=f[v][i]) 57 u=f[u][i],v=f[v][i]; 58 return f[u][0]; 59 }//基本操作 60 61 struct node{ 62 int st,ed,dist,lca; 63 bool operator <(const node x) 64 { 65 return dist<x.dist; 66 } 67 }plan[N]; 68 69 int n,m,ans; 70 71 int used[N]; 72 73 bool check(int len) 74 { 75 if(plan[m].dist<=len)return true; 76 for(int i=1;i<=n;i++)used[i]=0; 77 int x=0,maxn=0; 78 for(int i=m;i>=1;i--) 79 { 80 if(plan[i].dist<=len)break; 81 x++; 82 int u=plan[i].st,v=plan[i].ed,luv=plan[i].lca,c=plan[i].dist-len; 83 while(u!=luv) 84 { 85 if(up[u]>=c) 86 { 87 used[u]++; 88 maxn=maxn<used[u]?used[u]:maxn; 89 } 90 u=f[u][0]; 91 } 92 while(v!=luv) 93 { 94 if(up[v]>=c) 95 { 96 used[v]++; 97 maxn=maxn<used[v]?used[v]:maxn; 98 } 99 v=f[v][0]; 100 } 101 if(maxn<x)return false; 102 } 103 return true; 104 } 105 106 int main() 107 { 108 n=read(),m=read(); 109 for(int i=1,u,v,w;i<n;i++) 110 u=read(),v=read(),w=read(),add(u,v,w),add(v,u,w); 111 dfs(1,0,1); 112 for(int k=1;k<=19;k++) 113 for(int i=1;i<=n;i++) 114 f[i][k]=f[f[i][k-1]][k-1]; 115 for(int i=1,u,v;i<=m;i++) 116 { 117 u=read(),v=read(); 118 int luv=LCA(u,v); 119 plan[i]=(node){u,v,sum[u]+sum[v]-(sum[luv]<<1),luv}; 120 //预处理每个任务的时间和两个端点的LCA 121 } 122 sort(plan+1,plan+m+1); 123 int l=0,r=300000000; 124 while(l<r) 125 { 126 int mid=(l+r)>>1; 127 if(check(mid))r=mid,ans=mid; 128 else l=mid+1; 129 } 130 printf("%d\n",ans); 131 return 0; 132 }
做的时候并没有看题解，但貌似题解中有个人的思路几乎和我一样？