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;
}
感谢您的收看
