TOJ 192 路由器轉送量

TOJ 192 路由器轉送量

題目概述:

這題為102年全國賽第3題。http://toj.tfcis.org/oj/pro/192/

給n個點，每個點上有連接一些電腦。每個點的轉送量就是有多少電腦對會經過那個點，且a->b跟b->a算是不同的。

思路:

假設要算藍色的那個點，我們分成三個部分。

設全部電腦數all=28

1.非子孫走到子孫(扣自己) → (all-11)*(11-3)*2=272

2.自己走到全部→(all-3)*3*2=150

3.子孫走到子孫→ 6*(11-6-3)+2*(11-2-3)=12+12=24

4.自己的走到自己→ 3*(3-1)=6

總共是 452

//By SCJ

//TOJ 192

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

#define maxn 50000

int a[maxn],ch[maxn];//ch(含自己)

vector<int> G[maxn];

int all=0;

inline int dfs(int v,int p)

{

int res=0,ma=0;

for(int i:G[v])

{

if(i==p) continue;

ma=max(ma,dfs(i,v));

ch[v]+=ch[i];

}

ch[v]+=a[v];

res+=(ch[v]-a[v])*(all-ch[v])*2;

res+=a[v]*(a[v]-1);

res+=a[v]*(all-a[v])*2;

for(int i:G[v])

{

if(i==p) continue;

res+=(ch[v]-ch[i]-a[v])*ch[i];

}

return max(res,ma);

}

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

int n;

while(cin>>n,n!=0)

{

for(int i=0;i<n;++i) cin>>a[i],all+=a[i];

for(int i=1;i<n;++i)

{

int tp;cin>>tp;

G[i].push_back(tp);

G[tp].push_back(i);

}

cout<<dfs(0,-1)<<endl;

for(int i=0;i<n;++i) G[i].clear();all=0;

memset(ch,0,sizeof(ch));

}

}

/*

3

1 2 2

0 1

5

2 0 1 1 5

0 1 2 3

0

4

1 2 2 1

0 1 1

4

2 0 1 3

0 1 1

0

*/