做了这么多NOIPTG的题，这是唯一 一道一眼秒的T3(有时候T2还不会做QAQ)。。。
题目大意就不说了QWQ
思路大概是：啊最大值最小化，来个二分。检验mid的话，显然就是用最长路径减去所有边权>mid的边的交边中最大值，如果不大于mid就可行，那树上差分呀！（完）
神tmDay2 T1T3都有最大值最小化
之前写过加点权的树上差分，就是这题(戳我)。。。然后自己yy出了边的树上差分，其实和点一个道理，因为每个点的父亲边只有一条，于是给这个点加一个权值数组表示父亲边被使用的次数。每有一条路径(u,v)加入就cnt[u]++,cnt[v]++,cnt[lca(u,v)]-=2，那某个点x的父亲边被使用的次数就是x这棵子树的权值和辣！
一开始只拿了80分。。因为我在没有建好树的情况下，也就是刚刚读入两个点及其边权(x,y,z)时直接就val[y]++了，这时候还不知道x和y谁是父亲QAQ
代码如下：
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> using namespace std; struct poi{int too,pre,dis;}e[600010],lik[600010]; int n,m,x,y,z,l,r,mid,mx,val[300010],fa[300010],tot,tot2,q[300010][4],cntt[300010]; int cnt[300010],last[300010],last2[300010],d[300010]; bool v[300010]; void add(int x,int y,int z){e[++tot].too=y;e[tot].dis=z;e[tot].pre=last[x];last[x]=tot;} void add2(int x,int y,int z){lik[++tot2].too=y;lik[tot2].dis=z;lik[tot2].pre=last2[x];last2[x]=tot2;} int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);} void tarjan(int x) { v[x]=1;fa[x]=x; for(int i=last2[x];i;i=lik[i].pre)if(v[lik[i].too])q[lik[i].dis][3]=gf(lik[i].too); for(int i=last[x],too=e[i].too;i;i=e[i].pre,too=e[i].too)if(!v[too])d[too]=d[x]+e[i].dis,tarjan(too),fa[too]=x; } int dfs(int x,int fa) { int sum=cnt[x]; for(int i=last[x],too=e[i].too;i;i=e[i].pre,too=e[i].too)if(too!=fa)val[too]=e[i].dis,sum+=dfs(too,x); return cntt[x]=sum; } bool ck() { int total=0,mxx=0; memset(cnt,0,sizeof(cnt)); for(int i=1;i<=m;i++)if(d[q[i][1]]+d[q[i][2]]-2*d[q[i][3]]>mid)total++,cnt[q[i][1]]++,cnt[q[i][2]]++,cnt[q[i][3]]-=2; dfs(1,0); for(int i=1;i<=n;i++)if(cntt[i]==total&&val[i]>mxx)mxx=val[i]; return mx-mxx<=mid; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n-1;i++)scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z); for(int i=1;i<=m;i++)scanf("%d%d",&x,&y),add2(x,y,i),add2(y,x,i),q[i][1]=x,q[i][2]=y; tarjan(1); for(int i=1;i<=m;i++)mx=max(mx,d[q[i][1]]+d[q[i][2]]-2*d[q[i][3]]); l=0;r=mx; while(l<r) { mid=(l+r)/2; if(ck())r=mid;else l=mid+1; } printf("%d ",l); }