CF1578J Just Kingdom 题解

· · 题解

调了一下午……写一篇题解。

\text{Solution:}

首先考虑传送的过程，容易得到，传递过程的本质就是从小到大填儿子，如果这个填不满了，剩下的就平均分配。

那么，一个子树所需的流量显然就是 siz[x]. 如果一个点上面有 w 的流量，那么它父亲的其他孩子也必然都有一个 \min\{siz[v],w\} 的流量。

从上到下不好做，我们考虑能不能自底向上去推。由上述可以知道，一个点向上走，其父亲所需的流量对应会变为 \sum _{v\in fa} \min\{w,siz[v]\}

那么就可以模拟这个向上跳的过程了。

暴力？显然不太行，考虑继续发现性质。

首先对于所有 siz[x]>w 的节点， w 到其父亲上，就会至少加倍。因为 \min\{w,siz[x]\}=w, 对应到其父亲上面 w'\ge 2w.

所以，一个点向上倍增变大的次数一定不超过 \log v 次，也就是说，一个点跳到其父亲，不是将其父亲的所有孩子的 siz 全部加起来的次数，不超过 \log v 次。

那么，这个 “将所有兄弟的值全部加起来” 就可以启发我们做一点什么了，比如倍增优化。

而我们现在的任务就是处理哪些点是需要停下计算答案的。我们可以考虑一个倍增 dp.

设 t[i][j] 表示节点 i 向上跳 2^j 步，节点 i 的流量至少多大，才不会被倍增。

首先把上面说的一路加的数组求出来，设为 s[i][j], 那么对应 t 的转移式就应该是：

t[i][j]=\max\{t[i][j-1],t[fa[i][j-1]][j-1]-s[i][j-1]\}

意思就是要减去跳到 f[i][j-1] 处增加的增量。

那么对于特殊计算的答案，把一个点的儿子按照 siz 排序就可以二分处理答案了。

复杂度 O(n\log v\log n)

注意 t 的细节（就是因为这个改了一下午） t[i][0] 赋值的时候注意看看是不是恰好赋值成了他自己，如果是的话需要改为次大。

#include <bits/stdc++.h>
using namespace std;
typedef double db;
//#define int long long
#define fi first
#define se second
#define mk make_pair
#define pb emplace_back
#define poly vector<int>
#define Bt(a) bitset<a>
#define bc __builtin_popcount
#define pc putchar
#define ci const int&
#define DEBUG(x) printf("%d :",x),puts("--------------------------------------")
const int mod = 1e9 + 7;
const db eps = 1e-10;
const int inf = (1 << 30);
inline int Max(ci x, ci y) {return x > y ? x : y;}
inline int Min(ci x, ci y) {return x < y ? x : y;}
inline db Max(db x, db y) {return x - y > eps ? x : y;}
inline db Min(db x, db y) {return x - y < eps ? x : y;}
inline int Add(ci x, ci y, ci M = mod) {return (x + y) % M;}
inline int Mul(ci x, ci y, ci M = mod) {return 1ll * x * y % M;}
inline int Dec(ci x, ci y, ci M = mod) {return (x - y + M) % M;}
typedef pair<int, int> pii;
inline int Abs(int x) {return x < 0 ? -x : x;}
//char buf[1<<22],*p1=buf,*p2=buf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char Obuf[105000],*O=Obuf;//Siz shoule be the size of Out File
int pst[30],ptop;
inline void Fprint(){fwrite(Obuf,1,O-Obuf,stdout);}
inline void Fwrite(long long x){
  if(x==0){*O++='0';return;}
  if(x<0)*O++='-',x=-x;ptop=0;
  while(x)pst[++ptop]=x%10,x/=10;
  while(ptop)*O++=pst[ptop--]+'0';
  if(O-Obuf>100000)Fprint(),O=Obuf;
}
inline int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') w = -1;ch = getchar();}
    while (isdigit(ch)) {s = s * 10 + ch - '0';ch = getchar();}
    return s * w;
}
inline void write(long long x) {
    if (x < 0)putchar('-'), x = -x;
    if (x > 9)write(x / 10);
    pc(x % 10 + '0');
}
inline int qpow(int x, int y) {
    int res = 1;
    while (y) {if (y & 1)res = Mul(res, x);x = Mul(x, x);y >>= 1;}
    return res;
}
inline void cadd(int &x, int y) {x += y;}
inline void cmul(int &x, int y) {x *= y;}
inline void cmax(int &x, int y) {x = Max(x, y);}
inline void cmin(int &x, int y) {x = Min(x, y);}
const int N = 3e5+10;
const int SN = 20;
namespace Refined_heart{
    int pa[N],n,f[N][SN];
    long long s[N][SN],val[N],t[N][SN],mxv[N];
    int head[N],tot;
    struct E{int nxt,to;}e[N];
    inline void link(int x,int y){
        e[++tot]=(E){head[x],y};
        head[x]=tot;
    }
    vector<long long>G[N],pre[N];
    long long siz[N];
    void dfs1(int x){
        siz[x]=val[x];mxv[x]=0;f[x][0]=pa[x];
        for(int i=head[x];i;i=e[i].nxt){
            dfs1(e[i].to);
            siz[x]+=siz[e[i].to];
            G[x].pb(siz[e[i].to]);
        }
    }
    void dfs2(int x){
        for(int i=1;i<SN;++i)f[x][i]=f[f[x][i-1]][i-1];
        if(x){
            t[x][0]=mxv[pa[x]];
            if(siz[x]==t[x][0]&&G[pa[x]].size()>1)t[x][0]=G[pa[x]][(int)G[pa[x]].size()-2];
            else if(siz[x]==t[x][0])t[x][0]=0;
//          if(G[f[x][0]].size() == 1)t[x][0] = 0;
//          else t[x][0]=G[f[x][0]][(int)G[f[x][0]].size()-1-(G[f[x][0]][(int)G[f[x][0]].size()-1] == siz[x])];
            long long v=siz[pa[x]]-val[pa[x]];
            v-=siz[x];
            s[x][0]=v;
            for(int i=1;i<SN;++i)s[x][i]=s[x][i-1]+s[f[x][i-1]][i-1];
            for(int i=1;i<SN;++i)t[x][i]=max(t[x][i-1],t[f[x][i-1]][i-1]-s[x][i-1]);
        }
        for(int i=head[x];i;i=e[i].nxt){dfs2(e[i].to);}
    }
    void solve(){
        n=read();
        for(int i=1;i<=n;++i)pa[i]=read(),val[i]=read();
        for(int i=1;i<=n;++i){
            if(pa[i]==i)pa[i]=0;
            link(pa[i],i);
        }
        dfs1(0);
        for(int i=0;i<=n;++i)sort(G[i].begin(),G[i].end());
        for(int i=0;i<=n;++i){
            if(G[i].empty())continue;
            mxv[i]=G[i].back();
            pre[i].pb(G[i][0]);
            for(int j=1;j<(int)G[i].size();++j){
                long long v=pre[i].back();
                v+=G[i][j];
                pre[i].pb(v);
            }
        }
        dfs2(0);
        for(int i=1;i<=n;++i){
            int x=i;
            long long now=siz[i];
            while(x){
                for(int ii=SN-1;~ii;--ii){
                    if(x&&now>=t[x][ii]){
                        now+=s[x][ii];
                        x=f[x][ii];
                    }
                }
                if(!x)break;
                x=pa[x];
                int pos=upper_bound(G[x].begin(),G[x].end(),now)-G[x].begin();
                long long sn=now;
                if(pos>0)now+=pre[x][pos-1];
                now+=1ll*((int)G[x].size()-pos-1)*sn;
            }
            Fwrite(now);*O++='\n';
        }
        Fprint();
    }
}
signed main(){
//  freopen("in.txt","r",stdin);
//  freopen("My.out","w",stdout);
    Refined_heart::solve();
    return 0;
}