题解 P3128 【[USACO15DEC]最大流Max Flow】
XG_Zepto
2018-04-12 11:49:58
## 思路
实际上就是求被每个点被不同的路径覆盖了几次。只要把每条路径经过的点的答案加1即可。树剖和树状数组或线段树可以轻松搞定。
但是我们发现，这道题可以用LCA和树上查分更加优美而快速地解决。对于一条路径，将两个端点的值加1，它们的LCA和LCA的父亲分别减1，最后DFS累加一下就可以得到每个点的答案，取最大值即可。
## 代码
不同的模块写得非常清楚了，变量和函数解释如下：
- $l$数组和$head$数组：前向星存边。
- $s$数组：记录每个点的答案。
- $d$数组：每个点的深度。
- $p[i][j]$：第j个点向上走i^2步到达的点。
- $Pre$_$Work$函数：预处理出d和p。
- $Solve$函数：求LCA，单点修改。
- $Sum$函数：累加。
```
#include <bits/stdc++.h>
#define maxn 50001
using namespace std;
struct Edge{
int to,next;
Edge(int a=0,int b=0){
to=a,next=b;
}
}l[maxn*4];
int head[maxn],s[maxn],n,k,t1,t2;
int d[maxn],p[30][maxn],cnt,ans;
void Add(int x,int y){
l[++cnt]=Edge(y,head[x]);
head[x]=cnt;
}
void Pre_Work(int u,int f){
d[u]=d[f]+1;
p[0][u]=f;
for (int i=1;(1<<i)<=d[u];i++)
p[i][u]=p[i-1][p[i-1][u]];
for (int i=head[u];i;i=l[i].next){
int v=l[i].to;
if (v!=f) Pre_Work(v,u);
}
}
void Solve(int a,int b){
int lca;s[a]++,s[b]++;
if (d[a]<d[b]) swap(a,b);
for (int i=28;i>=0;i--)
if (d[p[i][a]]>=d[b]) a=p[i][a];
if (a==b) lca=a;
else {
for (int i=28;i>=0;i--)
if (p[i][a]!=p[i][b])
a=p[i][a],b=p[i][b];
lca=p[0][a];
}
s[lca]--;
s[p[0][lca]]--;
}
void Sum(int u,int f){
for (int i=head[u];i;i=l[i].next){
int v=l[i].to;
if (v==f) continue;
Sum(v,u);
s[u]+=s[v];
}
ans=max(s[u],ans);
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>k;
for (int i=1;i<n;i++){
cin>>t1>>t2;
Add(t1,t2);
Add(t2,t1);
}
Pre_Work(1,0);
for (int i=1;i<=k;i++){
cin>>t1>>t2;
Solve(t1,t2);
}
Sum(1,0);
cout<<ans<<endl;
}
```