简单树剖
没什么好讲的，只把几个操作说一下：
1、每一次操作都把x到y的点权都加1
2、最后查一下整个树的点权最大值
只需要对【模板】树链剖分 的线段树部分略加修改就OK了，修改就是把累加变成求最大值，简单得不行了。
代码：
#include<bits/stdc++.h>
#define maxn 4000001
#define L(x) (x<<1)
#define R(x) ((x<<1)|1)
using namespace std;
int tree[maxn],tag[maxn];
int rev[maxn],dep[maxn],size[maxn],seg[maxn],top[maxn],son[maxn],father[maxn];
int n,m,root,x,y,z,a[maxn],visx[maxn],visy[maxn],tot;
int cnt,from[maxn],to[maxn],Next[maxn],head[maxn];
char mode;
void add(int x,int y){
cnt++;
from[cnt]=x;to[cnt]=y;
Next[cnt]=head[x];head[x]=cnt;
}
void pushdown(int node,int begin,int end){
if(tag[node]){
tag[L(node)]+=tag[node];
tag[R(node)]+=tag[node];
int mid=(begin+end)>>1;
tree[L(node)]+=tag[node];
tree[R(node)]+=tag[node];
tag[node]=0;
}
}
void update(int node,int begin,int end,int x,int y,int val){
if(begin>y||end<x)return;
if(begin>=x&&end<=y){
tag[node]+=val;
tree[node]+=val;
return;
}else{
pushdown(node,begin,end);
int mid=(begin+end)>>1;
if(x<=mid)update(L(node),begin,mid,x,y,val);
if(y>mid) update(R(node),mid+1,end,x,y,val);
tree[node]=max(tree[L(node)],tree[R(node)]);
}
}
int query(int node,int begin,int end,int x,int y){
if(begin>=x&&end<=y){
return tree[node];
}else{
pushdown(node,begin,end);
int mid=(begin+end)>>1,sum=0;
if(x<=mid)sum=max(query(L(node),begin,mid,x,y),sum);
if(y>mid) sum=max(query(R(node),mid+1,end,x,y),sum);
return sum;
}
}
int dfs1(int x){
size[x]=1;
dep[x]=dep[father[x]]+1;
for(int i=head[x];i!=-1;i=Next[i]){
int v=to[i],big=0;
if(father[x]==v)continue;
father[v]=x;
big=dfs1(v);
size[x]+=big;
if(big>size[son[x]])son[x]=v;
}
return size[x];
}
void dfs2(int x){
if(son[x]){
seg[son[x]]=++seg[0];
top[son[x]]=top[x];
rev[seg[0]]=son[x];
dfs2(son[x]);
}
for(int i=head[x];i!=-1;i=Next[i]){
int v=to[i];
if(!top[v]){
seg[v]=++seg[0];
top[v]=v;
rev[seg[0]]=v;
dfs2(v);
}
}
}
int treequery(int x){
return query(1,1,seg[0],seg[x],seg[x]+size[x]-1);
}
void linkadd(int x,int y,int z){
int fx=top[x],fy=top[y];
while(fx!=fy){
if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
update(1,1,seg[0],seg[fx],seg[x],z);
x=father[fx];fx=top[x];
}
if(dep[x]>dep[y])swap(x,y);
update(1,1,seg[0],seg[x],seg[y],z);
}
int main(){
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);root=1;
for(int i=1;i<=n-1;i++){
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
dfs1(root);
seg[root]=++seg[0];
rev[seg[0]]=root;
top[root]=root;
dfs2(root);
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
linkadd(x,y,1);
}
printf("%d
",treequery(root));
}