因为准备学树剖于是又学了树差分。
点差分：u至v路径上所有点点权+1，那么c[u]++,c[v]++,c[lca]--,c[fa[lca]]--,可以在多次更新树链的点之后，得到某点权值
边差分：边差分的话要把边的权值存在他连着的儿子节点上，然后儿子节点的权值就是这条边的边权了，u至v路径上所有边的边权+1，那么c[u]++,c[v]++,c[lca]-=2,可以在多次更新树链之后，得到某边权值。
#include<bits/stdc++.h>
using namespace std;
#define fuck(x) cout<<#x<<" "<<x<<endl;
const int maxn=5e4+10;
int c[maxn];
vector<int>g[maxn];
int dep[maxn]; ///深度
int fa[maxn][40]; /// fa[i][j] 表示 i 节点的第 2^j 的祖先
int n,m; ///其中 m = log(n * 1.0) / log(2.0); n 为总数，编号为 1 ~ n;
void dfs1(int s,int f){
if(f != s) dep[s] = dep[f] + 1;
for(int j = 0;j < g[s].size();j ++){
int v = g[s][j];
if(v != f){
fa[v][0] = s;
for(int i = 1;i <= m;i ++)
fa[v][i] = fa[fa[v][i-1]][i-1];
dfs1(v,s);
}
}
}
int lca(int u,int v){ ///u,v的最近公共祖先
if(dep[u] < dep[v]) swap(u,v); ///u 在下面
int d = dep[u] - dep[v];
for(int i = 0; (1 << i) <= d;i ++) ///移动到相同深度
if((1 << i) & d) ///(1<<i)&f找到f化为2进制后1的位置，移动到相应的位置
u = fa[u][i]; ///比如f=5(101),先移动2^0祖先，然后再移动2^2祖先
if(u != v){
for(int i = m;i >= 0;i --)
if(fa[u][i] != fa[v][i]) ///从最大祖先开始，判断a,b祖先，是否相同
u = fa[u][i], v = fa[v][i]; ///如不相同，a b同时向上移动2^j
u = fa[u][0];
}
return u;
}
void dfs2(int now,int fa)
{
for(int i=0;i<g[now].size();i++)
{
int v=g[now][i];
if(v==fa) continue;
dfs2(v,now);
c[now]+=c[v];
}
}
int main()
{
int k,maxx=0;
scanf("%d%d",&n,&k);
m=log(n * 1.0)/log(2.0);
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1,0);
while(k--)
{
int x,y,tmp;
scanf("%d%d",&x,&y);
tmp=lca(x,y);
c[x]++;c[y]++;c[tmp]--;c[fa[tmp][0]]--;
}
dfs2(1,0);
for(int i=1;i<=n;i++){
maxx=max(maxx,c[i]);
}
cout<<maxx<<endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define fuck(x) cout<<#x<<" "<<x<<endl;
const int maxn=3e5+10;
struct node
{
int v,w,nxt;
node(int v=0,int w=0,int nxt=0)
{
this->v=v;
this->w=w;
this->nxt=nxt;
}
}e[maxn<<1];
struct myplan
{
int u,v,dis,lc;
myplan(int u=0,int v=0,int dis=0,int lc=0)
{
this->u=u;
this->v=v;
this->dis=dis;
this->lc=lc;
}
friend bool operator<(const myplan&mm,const myplan&gg)
{
return mm.dis<gg.dis;
}
}plan[maxn];
int n,pn,m,maxe,pos,head[maxn],dis[maxn],fa[maxn][30],dep[maxn],lb[maxn],c[maxn];
inline int read()
{
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
inline void dfs1(int u,int f,int di)
{
dep[u]=dep[f]+1;
dis[u]=dis[f]+di;
for(register int i=head[u];i;i=e[i].nxt){
int v = e[i].v;
if(v != f){
fa[v][0] = u;
for(register int j = 1;j <= m;++j)
fa[v][j] = fa[fa[v][j-1]][j-1];
dfs1(v,u,e[i].w);
}
}
}
inline int lca(int u,int v){ ///u,v的最近公共祖先
if(dep[u] < dep[v]) swap(u,v); ///u 在下面
int d = dep[u] - dep[v];
for(register int i = 0; (1 << i) <= d;++i) ///移动到相同深度
if((1 << i) & d) ///(1<<i)&f找到f化为2进制后1的位置，移动到相应的位置
u = fa[u][i]; ///比如f=5(101),先移动2^0祖先，然后再移动2^2祖先
if(u != v){
for(register int i = m;i >= 0;--i)
if(fa[u][i] != fa[v][i]) ///从最大祖先开始，判断a,b祖先，是否相同
u = fa[u][i], v = fa[v][i]; ///如不相同，a b同时向上移动2^j
u = fa[u][0];
}
return u;
}
inline void dfs2(int now,int f,int di)
{
for(register int i=head[now];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(v==f) continue;
dfs2(v,now,w);
c[now]+=c[v];
}
if(c[now]==pn-pos+1)
maxe=max(maxe,di);
}
inline bool check(int mid)
{
pos=upper_bound(lb+1,lb+pn+1,mid)-lb;
if(pos==pn+1)
return true;
for(register int i=1;i<=n;i++) c[i]=0;
for(register int i=pos;i<=pn;++i)
{
c[plan[i].u]++;c[plan[i].v]++;c[plan[i].lc]-=2;
}
maxe=-1;
dfs2(1,0,0);
// if(mid==11)
// {
// cout<<"pos"<<pos<<endl;
// cout<<"maxe"<<maxe<<endl;
// }
if(maxe==-1)
return false;
if(plan[pn].dis-maxe<=mid)
return true;
return false;
}
int main()
{
int cnt=0,low,high,mid,ans;
n=read();
pn=read();
m=(log(n*1.0)/log(2.0))+1;
for(register int i=1;i<n;++i)
{
int u,v,w;
u=read();
v=read();
w=read();
e[++cnt]=node(v,w,head[u]);
head[u]=cnt;
e[++cnt]=node(u,w,head[v]);
head[v]=cnt;
}
dfs1(1,0,0);
for(register int i=1;i<=pn;++i){
plan[i].u=read();plan[i].v=read();plan[i].dis=dis[plan[i].u]+dis[plan[i].v]-2*dis[plan[i].lc=lca(plan[i].u,plan[i].v)];
}
sort(plan+1,plan+pn+1);
for(int i=1;i<=pn;i++) lb[i]=plan[i].dis;
// cout<<"plan"<<endl;
// for(int i=1;i<=pn;i++) cout<<plan[i].u<<" "<<plan[i].v<<" "<<plan[i].dis<<endl;
// cout<<"end"<<endl;
low=0,high=plan[pn].dis;
while(low<=high)
{
mid=(low+high)>>1;
//fuck(mid);
if(check(mid))
ans=mid,high=mid-1;
else
low=mid+1;
}
printf("%d
",ans);
return 0;
}