AGC029 E: Wandering TKHS

╰+哭是因爲堅強的太久メ 2021-11-13 15:36 235阅读 0赞

![favicons_domain_agc029.contest.atcoder.jp][] [E: Wandering TKHS - AtCoder Grand Contest 029 | AtCoder][E_ Wandering TKHS - AtCoder Grand Contest 029 _ AtCoder]

分类讨论好题（也不太算分类讨论）

方法：感受过程手玩，考虑能不能提前预算一些东西，或者递推，递归

**也就是，找问题划分点**

关注一个点x到根节点的最大值mx\[x\]（包括自己）

因为最大值的父亲fa\[mx\[x\]\]的ans一定不会扩展mx\[x\]

所以求出mx\[x\]

### 对于mx\[x\]!=x情况 ###

定义son\[x\]，x的mx\[x\]往x方向走的第一个儿子

x一定会历经艰难扩展到mx，期间son\[x\]子树内，mx\[\*\]=mx\[x\]的\*都会被扩展。第一部分

走到了mx

之后，son\[x\]子树不会有任何扩展，

但是还可能会扩展一些mx除了son\[x\]的其他子树点y

如果y到根的次大值（最大值一定也是mx）是mx到根的次大值se\[mx\]的话，那么一定在次大值及之前会被扩展。第二部分

所以，次大值也关心。

然后就是ans\[fa\[mx\]\]了，之前已经算过，而且不会算重！第三部分

子树某个值出现次数

第一部分线段树合并

第二部分线段树合并，再减去son\[x\]子树的贡献

### 对于mx\[x\]==x情况 ###

更好处理

直接变成上述情况的第二部分。mx子树内，se\[\*\]=se\[x\]的个数

线段树合并。

代码：

#include<bits/stdc++.h>
    #define reg register int
    #define il inline
    #define fi first
    #define se second
    #define mk(a,b) make_pair(a,b)
    #define numb (ch^'0')
    #define pb push_back
    #define solid const auto &
    #define enter cout<<endl
    #define pii pair<int,int>
    using namespace std;
    typedef long long ll;
    template<class T>il void rd(T &x){
        char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
        for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);}
    template<class T>il void output(T x){
        if(x/10)output(x/10);putchar(x%10+'0');}
    template<class T>il void ot(T x){
        if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
    template<class T>il void prt(T a[],int st,int nd){
        for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
    namespace Modulo{
    const int mod=998244353;
    int ad(int x,int y){
        return (x+y)>=mod?x+y-mod:x+y;}
    void inc(int &x,int y){x=ad(x,y);}
    int mul(int x,int y){
        return (ll)x*y%mod;}
    void inc2(int &x,int y){x=mul(x,y);}
    int qm(int x,int y=mod-2){
        int ret=1;while(y){
        if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;}
    }
    //using namespace Modulo;
    namespace Miracle{
    const int N=2e5+5;
    int n;
    struct node{
        int nxt,to;
    }e[2*N];
    int hd[N],cnt;
    void add(int x,int y){
        e[++cnt].nxt=hd[x];
        e[cnt].to=y;
        hd[x]=cnt;
    }
    int se[N],mx[N];
    int son[N];
    int pa[N];
    void dfs(int x,int fa){
        se[x]=se[fa];
        mx[x]=mx[fa];
        if(x>mx[x]){
            se[x]=mx[x];mx[x]=x;
        }else se[x]=max(se[x],x);
        if(mx[x]==mx[fa]){
            if(mx[fa]==fa) son[x]=x;
            else son[x]=son[fa];
        }
        for(reg i=hd[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(y==fa) continue;
            pa[y]=x;
            dfs(y,x);
        }
    }
    struct tr{
        int ls,rs;
        int cnt[2];
    }t[N*60];
    int tot;
    int rt[N];
    #define mid ((l+r)>>1)
    void upda(int &x,int l,int r,int p,int c){
        if(!x) x=++tot;
        if(l==r){
            t[x].cnt[c]++;return;
        }
        if(p<=mid) upda(t[x].ls,l,mid,p,c);
        else upda(t[x].rs,mid+1,r,p,c);
    }
    int merge(int x,int y,int l,int r){
        if(!x||!y) return x+y;
        if(l==r){
            t[x].cnt[0]=t[x].cnt[0]+t[y].cnt[0];
            t[x].cnt[1]=t[x].cnt[1]+t[y].cnt[1];
            return x;
        }
        t[x].ls=merge(t[x].ls,t[y].ls,l,mid);
        t[x].rs=merge(t[x].rs,t[y].rs,mid+1,r);
        return x;
    }
    void dfs2(int x,int fa){
        upda(rt[x],1,n,mx[x],1);
        upda(rt[x],1,n,se[x],0);
        for(reg i=hd[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(y==fa) continue;
            dfs2(y,x);
            rt[x]=merge(rt[x],rt[y],1,n);
        }
    }
    int query(int x,int l,int r,int p,int c){
        if(!x) return 0;
        if(l==r) return t[x].cnt[c];
        if(p<=mid) return query(t[x].ls,l,mid,p,c);
        else return query(t[x].rs,mid+1,r,p,c);
    }
    int ans[N];
    void fin(int x,int fa){
        if(x!=1){
            if(mx[x]!=x){
                int A=query(rt[son[x]],1,n,mx[x],1),B=query(rt[mx[x]],1,n,se[mx[x]],0),C=-query(rt[son[x]],1,n,se[mx[x]],0),D=ans[pa[mx[x]]];
                // cout<<" xx "<<x<<" : "<<A<<" "<<B<<" "<<C<<" "<<D<<endl;
                ans[x]=A+B+C+D;
            }else{
                ans[x]=query(rt[x],1,n,se[x],0)+ans[fa];
            }
        }
        for(reg i=hd[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(y==fa) continue;
            fin(y,x);
        }
    }
    int main(){
        rd(n);int x,y;
        for(reg i=1;i<n;++i){
            rd(x);rd(y);
            add(x,y);add(y,x);
        }
        dfs(1,0);
        dfs2(1,0);
        // prt(se,1,n);
        // prt(mx,1,n);
        // prt(son,1,n);
        fin(1,0);
        prt(ans,2,n);
        return 0;
    }
    
    }
    signed main(){
        Miracle::main();
        return 0;
    }
    
    /*
       Author: *Miracle*
    */

mx的发现很关键，以mx位置为划分点，可以把问题分成若干部分处理，

由于fa\[mx\]不会再进入mx，还支持递归！

转载于:https://www.cnblogs.com/Miracevin/p/10975883.html

[favicons_domain_agc029.contest.atcoder.jp]: https://www.google.com/s2/favicons?domain=agc029.contest.atcoder.jp
[E_ Wandering TKHS - AtCoder Grand Contest 029 _ AtCoder]: https://agc029.contest.atcoder.jp/tasks/agc029_e