一.题目
P3128 [USACO15DEC] Max Flow P - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
二 .分析
我们可以先建一棵树
但我们发现,这样会超时。
所以,我们想到树上差分文章来源:https://www.toymoban.com/news/detail-628505.html
文章来源地址https://www.toymoban.com/news/detail-628505.html
三.代码
/*
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;
}
到了这里,关于【图论】树上差分(点差分)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!