Max Flow P

题目传送门

题目大意

题目大意就是给你一棵树，再给你K次操作将x到y的所有点的值都加1，然后输出所有点值的最大值。

思路

这一题如果用暴力的话从范围来看肯定会T(tle)所以我们要考虑用差分的思想去做。

代码

先看代码：

#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){
      // 最近公共祖先初始化
	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的层数和y的层数相等
	{
    
		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];// 返回祖先编号
}
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]]--; // 更新需要更新的节点的差分
	}
	dfs(1,0);
	cout << ans <<endl;
	return 0;
}

感谢您的收看