【图论】树上差分（点差分）

一.题目

 输入样例：

5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5 
3 4

输出样例：9

---

二 .分析

我们可以先建一棵树

但我们发现，这样会超时。

所以，我们想到树上差分

 

三.代码

/*
5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5 
3 4
*/#include<bits/stdc++.h>
#define maxn 500005
using namespace std;
int n,m;
int head[maxn],depth[maxn],p[maxn][25],d[maxn];
struct Edge{int u,v,next;
}edge[maxn<<1];
int cnt=0;
void add(int u,int v){edge[++cnt]=(Edge){u,v,head[u]}; head[u]=cnt;
}
void dfs(int u,int fa){depth[u]=depth[fa]+1;p[u][0]=fa;for(int i=1;(1<<i)<=depth[u];i++){p[u][i]=p[p[u][i-1]][i-1];}for(int i=head[u];i;i=edge[i].next){int v=edge[i].v;if(v!=fa){dfs(v,u);}}
}
int lca(int x,int y){if(depth[x]<depth[y]) swap(x,y);int lg=0;while((1<<lg)<=depth[x]) lg++;for(int i=lg;i>=0;i--){if(depth[x]-(1<<i)>=depth[y]) x=p[x][i];}if(x==y) return x;for(int i=lg;i>=0;i--){if(p[x][i]!=p[y][i]){x=p[x][i]; y=p[y][i];}}return p[x][0];
}
void dfs2(int u,int fa){for(int i=head[u];i;i=edge[i].next){int v=edge[i].v;if(v!=fa){dfs2(v,u);d[u]+=d[v];}}
}
int main(){cin>>n>>m;for(int i=1;i<=n-1;i++){int u,v;cin>>u>>v;add(u,v);add(v,u);}dfs(1,0); //建树 while(m--){int u,v; cin>>u>>v;d[u]++; d[v]++;int lc=lca(u,v);d[lc]--; d[p[lc][0]]--;}dfs2(1,0); //sum求原数组 int ans=0;for(int i=1;i<=n;i++){ans=max(ans,d[i]);}cout<<ans;return 0;
}