秒切树上查分....（最近一次集训理解的东西）
但是，我敲了半小时才切掉这道题....
我一直迷在了“边差分”和“点差分”的区别上。
所以，先说一下此题，再说一下区别。
首先，想到差分很容易。
然后，按照戴大爷的说法，x++，y++，lca（x，y）-=2；
这是模板，统计的是每条边被经过几次。理解一下，向上前缀和时，lca向上的那条边，会被计算两次，我们既不希望它被记录，也不希望它被记录两次。
所以，要消除前面的影响，就要把它在lca“断掉”，所以只要消除这条边的影响就行了，实现就是-2；
但是，这题，要求的是点的经过数，所以，貌似不太一样了。
继续考虑，怎么消除影响而且不影响lca那个点。
首先，lca要被记录一次，但是边差分时，为了消除影响，我们减了2次。所以，可以想到，-1即可。
但是，上面的点怎么办呢？怎么消除影响呢？
很简单啊，只要把lca的father给删掉，就可以啦。
也就是fa【lca】-1;
于是，只要点差分就可以了。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int n,m;
struct edge
{
int to,next;
}e[maxn];
int head[maxn],cnt;
inline void addedge(int from,int to)
{
e[++cnt].next=head[from];
e[cnt].to=to;
head[from]=cnt;
}
int dep[maxn];
int fa[maxn][50];
int son[maxn];
void dfs(int u,int f)
{
dep[u]=dep[f]+1;
fa[u][0]=f;
son[f]=u;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(v==f)
continue;
dfs(v,u);
}
}
int lca(int a,int b)
{
if(dep[a]>dep[b])
swap(a,b);//a<b
for(int i=30;i>=0;i--)
{
if(dep[b]-(1<<i)>=dep[a])
b=fa[b][i];
}
if(a==b)
return a;
for(int i=30;i>=0;i--)
{
if(fa[a][i]!=fa[b][i])
{
a=fa[a][i];
b=fa[b][i];
}
}
return fa[a][0];
}
int dis[maxn],ans;
void dfs2(int u,int f)
{
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(v==f)
continue;
dfs2(v,u);
dis[u]+=dis[v];
}
}
int main()
{
//freopen("zdl.in","r",stdin);
//freopen("zdl.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
dfs(1,0);
for(int i=1;i<=30;i++)
{
for(int j=1;j<=n;j++)
{
fa[j][i]=fa[fa[j][i-1]][i-1];
}
}
while(m--)
{
int x,y;
scanf("%d%d",&x,&y);
int t=lca(x,y);
dis[x]++;
dis[y]++;
dis[t]-=1;
dis[fa[t][0]]-=1;
}
dfs2(1,0);
for(int i=1;i<=n;i++)
{
ans=max(dis[i],ans);//printf("%d ",dis[i]);
}
printf("%d",ans);
return 0;
}
（完）
原文：https://www.cnblogs.com/ajmddzp/p/11815796.html