123. bx和妹子的游戏

题目描述

这天，$bx$和妹子在一个有根树上玩游戏。

这个有根树有$n$个节点，编号从$1$到$n$，其中$1$号节点是根节点。除了$1$号节点每个节点都有一个父亲节点。第$i$个节点有权值a_ia​i​​。

定义$s(u,v)$为$u$到$v$的简单路径上所有点的权值之和（包括$u$和$v$）。

$bx$会随机选一个节点$u$，妹子随机选一个节点$v$，假设$u$和$v$的$LCA$为$p$，$bx$能获得$\max (s(u,p),s(v,p))$的愉悦值。

现在你需要回答，考虑所有情况之下（n^2n​2​​种情况），$bx$所获得的愉悦值之和。

一个节点$u$的祖先定义为从$u$一直往父亲节点走若干次能到达的节点，其中$u$是自身的祖先。两个节点的$LCA$（最近公共祖先）定义为既是$u$的祖先，也是$v$的祖先，并且和$u$的距离最近的一个节点。

输入格式

输入第一行包括一个整数$T$，表示数据组数。

对于每组数据，第一行一个整数$n$。

第二行$n-1$个整数，第$i$个整数表示节点$i+1$的父亲p_{i+1}p​i+1​​。

第三行$n$个整数，第$i$个整数表示节点i的权值a_ia​i​​。

$1\le T\le 20$

$2\le n\le 100000$

1 \le p_{i + 1} \le i, 1 \leq i \leq n - 11≤p​i+1​​≤i,1≤i≤n−1

1 \leq a_i \leq 100001≤a​i​​≤10000

输出格式

对每组数据,输出 bx 获得的愉悦值之和。

样例数据

输入

2 3 1 1 1 2 3 2 1 1 2

输出

28 9

max( S[u,p] , S[v,p] ) = max( S[1,u] , S[1,v] ) - ( S[1,p] - a[p] )

显然可以在O(n)内求出S[1,k]

S[1,i]对答案的贡献=

S[1,p]-a[p] 对答案的贡献为 = - ( p 作为 lca 的次数 * (S[1,p]-a[p]) )

#include<iostream> #include<cstdlib> #include<cstdio> #include<string> #include<vector> #include<deque> #include<queue> #include<algorithm> #include<set> #include<map> #include<stack> //#include<cti1me> #include<string.h> #include<math.h> #include<list> using namespace std; #define ll long long #define pii pair<int,int> const int inf = 1e9+7; const int N = 100000 + 5; struct Edge{ int to,next; }edge[N]; int head[N]; int a[N]; void addEdge(int k,int u,int v){ edge[k].to=v; edge[k].next=head[u]; head[u]=k; } ll s[N]; ll childs[N]; ll tS[N]; void dfs(int u,int sum){ s[u]=sum+a[u]; childs[u]=1; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; dfs(v,s[u]); childs[u]+=childs[v]; } } ll f(int u){//u作为lca有多少种情况 ll ans=1; for(int i=head[u];i!=-1;i=edge[i].next){ int x=edge[i].to; ans+=childs[x]; for(int j=edge[i].next;j!=-1;j=edge[j].next){ int y=edge[j].to; ans+=childs[x]*childs[y]; } } return ans; } ll slove(int n){ dfs(1,0); ll ans=0; for(int i=1;i<=n;++i){ tS[i]=s[i]; } sort(s+1,s+n+1); for(int i=1;i<=n;++i){ ans+=s[i]*i; ans-=f(i)*(tS[i]-a[i]); } return ans; } int main() { //freopen("/home/lu/Documents/r.txt","r",stdin); //freopen("/home/lu/Documents/w.txt","w",stdout); int T; scanf("%d",&T); while(T--){ int n; scanf("%d",&n); fill(head,head+n+1,-1); int nume=0; for(int i=2;i<=n;++i){ int p; scanf("%d",&p); addEdge(nume++,p,i); } ll sub=0; for(int i=1;i<=n;++i){ scanf("%d",&a[i]); sub+=a[i]; } printf("%lld\n",2*slove(n)-sub); } return 0; }