Max Flow P

题目传送门

题目大意

题目大意就是给你一棵树,再给你K次操作将x到yThe values ​​of all points of are added1,Then output the maximum value of all point values.

思路

If this question uses violence, it will definitely be in terms of scopeT(tle)So we have to consider using the idea of ​​difference to do it.

代码

先看代码：

#include<bits/stdc++.h>
#define N 2000005
using namespace std;
int f[N][30],cnt[N],d[N],x,y,n,k,l,ans=-123456789;
vector <int> g[N];
queue <int> q;
void bfs(int t){
      // Most recent common ancestor initialization
	queue <int> q;
	q.push(t);
	d[t]=1;
	while(q.size()){
     // 使用广搜bfs
		int x=q.front();
		q.pop();
		for(int i=0;i<g[x].size();i++){
    
			int y = g[x][i];
			if(d[y])continue;
			d[y] = d[x]+1;
			f[y][0] = x;
			for(int j=1;j<=l;j++){
    
				f[y][j] = f[f[y][j-1]][j-1];
			} 
			q.push(y);
		}
	}
} 
int lca(int x,int y){
     // 获取x和y的最近公共祖先
	if(d[x]>d[y])swap(x,y);
	for(int i=l;i>=0;i--) // 让x的层数和yequal number of layers
	{
    
		if(d[f[y][i]]>=d[x]){
    
			y = f[y][i];
		}
	}
	if(x==y)return x;
	for(int i=l;i>=0;i--){
    
		if(f[x][i]!=f[y][i]){
    
			x = f[x][i],y=f[y][i];  
		}
	}
	return f[x][0];// Returns the ancestor number
}
int dfs(int x,int fa){
     // 统计最大值
	int an=0;
	for(int i=0;i<g[x].size();i++){
    
		int y = g[x][i];
		if(fa==y)continue;
		dfs(y,x);
		cnt[x] += cnt[y]; 
	}
	ans = max(ans,cnt[x]);
}
signed main(){
     // 主函数
	ios::sync_with_stdio(false),cin.tie(0),cin.tie(0);
	cin >> n >> k;
	l = log2(n)+1; 
	for(int i=1;i<n;i++){
    
		cin >>x>>y;
		g[x].push_back(y);
		g[y].push_back(x); // 建图
	} 
	bfs(1);
	for(int i=1;i<=k;i++){
    
		cin >> x>> y;
		int lxy=lca(x,y);
		cnt[x]++;cnt[y]++;cnt[lxy]--;cnt[f[lxy][0]]--; // Update the difference of the nodes that need to be updated
	}
	dfs(1,0);
	cout << ans <<endl;
	return 0;
}

感谢您的收看