hello.

题解 P3128 【[USACO15DEC]最大流Max Flow】

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;
    }