2017杭电ACM集训队单人排位赛 - 6 [Problem 1001]

201707 （ACM）思维

题意

题解

• s[u][p]=dis[u]-dis[fp]
• 然后算贡献就行

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define sz(a) (int)a.size()
//---------------
const int N=100005;
int fa[N],w[N],dis[N],tson[N];
ll clca[N],sclca[N];
vector<int> son[N];
void dfs(int u) {
    dis[u]=dis[fa[u]]+w[u];
    tson[u]=1;
    rep(i,0,sz(son[u])) {
        int v=son[u][i];
        dfs(v);
        tson[u]+=tson[v];
    }
}
void dfs2(int u) {
    clca[u]=tson[u];
    rep(i,0,sz(son[u])) {
        int v=son[u][i];
        clca[u]=clca[u]+1ll*tson[v]*(tson[u]-tson[v]);
        dfs2(v);
    }
}
int main() {
    int T;scanf("%d",&T);
    while(T--) {
        ///
        int n;scanf("%d",&n);
        ///init
        rep(i,0,n+1) son[i].clear();
        memset(sclca,0,sizeof(sclca));
        memset(fa,0,sizeof(fa));
        memset(w,0,sizeof(w));
        memset(dis,0,sizeof(dis));
        memset(tson,0,sizeof(tson));
        memset(clca,0,sizeof(clca));
        ///read
        rep(i,2,n+1) {
            int x;scanf("%d",&x);
            fa[i]=x;
            son[x].pb(i);
        }
        rep(i,1,n+1) scanf("%d",w+i);
        ///get dis tson
        dfs(1);
        ///get clca
        dfs2(1);
        ///get sclca
        rep(i,1,n+1) sclca[fa[i]]+=clca[i];
        ///solve
        ll ans=0;
        rep(i,1,n+1) {
            ans=ans-1ll*dis[i]*sclca[i];
        }
        sort(dis+1,dis+1+n);
        rep(i,1,n+1) {
            ans=ans+1ll*dis[i]*(2*i-1);
        }
        ///print
        printf("%lld\n",ans);
    }
    return 0;
}