---恢复内容开始---
题目大意：给你一颗树，你可以把其中一条边的边权改成0，使给定的一些树链的权值和的最大值最小
把lenth定义为未修改边权时的答案
考虑二分答案，如果二分的答案成立，设修改成0的边边权为k，那么所有原链长>mid的链都要被这条边影响，显然这些链存在边权为k的公共边
那么我们二分出一个答案，然后把所有原链长>mid的链在树上打差分来记录每条边被覆盖多少次
如果某条边的满足lenth-边权<=mid 且 这条边被覆盖次数==原链长>mid的链数，说明这条边作为0边可行。
会卡常，据说树剖不会被卡但我用了结果还是被卡了。懒得优化了
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 300100
using namespace std; int n,m,cte,mxl,cnt,lth,ct,idd;
int head[N],sz[N],tp[N],hvy[N],fa[N],dep[N],dif[N],sum[N],d[N],dis[N];
struct EDGE{
int to,nxt,val;
}edge[N*];
struct FLY{
int x,y,ff,len;
}fly[N];
void edge_add(int u,int v,int w)
{
cte++;
edge[cte].to = v;
edge[cte].nxt= head[u];
edge[cte].val= w;
head[u]=cte;
}
int gc()
{
int rett=,fh=;char p=getchar();
while(p<''||p>'') {p=getchar();}
while(p>=''&&p<='') {rett=rett*+p-'';p=getchar();}
return rett*fh;
}
void dfs_order1(int u,int dad)
{
int h=,id=;
for(int j=head[u];j!=-;j=edge[j].nxt)
{
int v=edge[j].to;
if(v==dad) continue;
dis[v]=dis[u]+edge[j].val;
dep[v]=dep[u]+;
dfs_order1(v,u);
d[v]=edge[j].val;
fa[v]=u;
if(sz[v]>h) h=sz[v],id=v;
sz[u]+=sz[v];
}
sz[u]++;
if(head[u]==-) return;
hvy[u]=id;
}
void dfs_order2(int u,int dad,int tpp)
{
tp[u]=tpp;
if(hvy[u]) tp[hvy[u]]=tp[u],dfs_order2(hvy[u],u,tpp);
for(int j=head[u];j!=-;j=edge[j].nxt)
{
int v=edge[j].to;
if(v==dad||v==hvy[u]) continue;
dfs_order2(v,u,v);
}
}
void dfs_maxlenth(int u,int dad)
{
sum[u]+=dif[u];
for(int j=head[u];j!=-;j=edge[j].nxt)
{
int v=edge[j].to;
if(v==dad) continue;
dfs_maxlenth(v,u);
sum[u]+=sum[v];
}
if(sum[u]>=ct&&d[u]>mxl) idd=u,mxl=d[u];
}
int LCA(int x,int y)
{
while(tp[x]!=tp[y])
{
if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
x=fa[tp[x]];
}
return dep[x]<=dep[y]?x:y;
}
bool check(int mid)
{
memset(sum,,sizeof(sum));
mxl=,ct=;;
for(int i=;i<=m;i++)
if(fly[i].len>mid)
{
sum[fly[i].x]++,sum[fly[i].y]++;
sum[fly[i].ff]-=;
ct++;
}
dfs_maxlenth(,-);
if(lth-mxl<=mid) return ;
else return ;
} int main()
{
//freopen("testdata.in","r",stdin);
scanf("%d%d",&n,&m);
memset(head,-,sizeof(head));
int x,y,z;
for(int i=;i<n;i++)
{
x=gc(),y=gc(),z=gc();
edge_add(x,y,z);
edge_add(y,x,z);
}
dfs_order1(,-);
tp[]=;
dfs_order2(,-,);
lth=;
for(int i=;i<=m;i++)
{
fly[i].x=gc(),fly[i].y=gc();
fly[i].ff=LCA(fly[i].x,fly[i].y);
fly[i].len=dis[fly[i].x]+dis[fly[i].y]-*dis[fly[i].ff];
lth=max(lth,fly[i].len);
}
int l=,r=;
r=lth;
int ret=;
while(l<r)
{
int mid=(l+r)>>;
if(check(mid)) r=mid,ret=mid;
else l=mid+;
}
printf("%d",ret);
return ;
}
---恢复内容结束---