ZOJ 3715 Kindergarten Election

ZOJ 3715 Kindergarten Election

At the beginning of the semester in kindergarten, the n little kids (indexed from 1 to n, for convenience) in class need to elect their new leader.

The i^th kid will vote for his best friend f_i (where 1 ≤ f_i ≤ n, and it's too shame to vote for yourself, so f_i ≠ i). And the kid who gets the most votes will be the leader. If more than one kids who get the largest number of votes, there will be multiple leaders in the new semester.

Little Sheldon (the kid with index 1) is extremely vain, and he would like to be the ONLY leader. (That means the number of votes he gets should strictly larger than any other.) Soon Sheldon found that if he give c_icandies to the i^th kid, the i^th kid would regard Sheldon as the new best friend, and of course vote for Sheldon.

Every kid including Sheldon loves candies. As an evil programmer, please help the evil Sheldon become the ONLY leader with minimum cost of candies. By the way, Sheldon should vote for any one he wantsEXCEPT himself.

Input

There are multiple test cases. The first line of input contains an integer T (T ≤ 100) indicating the number of test cases. Then T test cases follow.

The first line of each case contains one integer: n (3 ≤ n ≤ 100) -- the number of kids in class.

The second line contains n-1 integers: f_i (1 ≤ f_i ≤ n, f_i ≠ i, and 2 ≤ i ≤ n) -- represents that the best friend of i^th kid is indexed with f_i.

The third line contains n-1 integers: c_i (1 ≤ c_i ≤ 1000, and 2 ≤ i ≤ n) -- represents that if Sheldon gave c_i candies to the i^th kid, the i^th kid would vote Sheldon, instead of their old best friend f_i, as the new semester leader.

Output

For each test case, print the minimal cost of candies to help Sheldon become the ONLY leader.

Sample Input

2
4
1 1 2
1 10 100
3
3 2
1 10

Sample Output

0
11

Hint

In the first case,

• If Sheldon vote for 2^nd kid, the 2^nd kid and Sheldon will both have 2 votes. In this case, Sheldon have to pay 100 candies to the 4^th kid, and get 3 votes to win;

• If Sheldon vote for 3^rd or 4^th kid, Sheldon will win with 2 votes without sacrifice any candy.

枚举孩子赢的选举得到的票数p，所有大于等于p的孩子都要减到p-1如果发现，减去之后的票数给那个主角发现他比p大了，那么这个情况就是不实际的。否则，就在剩下的票里面从小到大选择直到票数等于p。这里的有一个条件，主角自己有票，其实是不用考虑的，这里不证明了

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>using namespace std;
#define MAX 10000000
struct Node
{int pos;int value;
}c[105],v[105][105];
int n;
int cmp(Node a,Node b)
{return a.value<b.value;
}
int f[105];
int num[105];
int tag[105];
int ans;
int s[105];
int main()
{int t;scanf("%d",&t);while(t--){scanf("%d",&n);memset(num,0,sizeof(num));for(int i=2;i<=n;i++){scanf("%d",&f[i]);v[f[i]][++num[f[i]]].pos=i;}for(int i=2;i<=n;i++){scanf("%d",&c[i].value);c[i].pos=i;}for(int i=2;i<=n;i++)for(int j=1;j<=num[i];j++)v[i][j].value=c[v[i][j].pos].value;for(int i=2;i<=n;i++)sort(v[i]+1,v[i]+1+num[i],cmp);sort(c+1,c+1+n,cmp);ans=MAX;for(int p=num[1];p<=n;p++){int l=p-num[1];int sum1=0;int sum2=0;memset(s,0,sizeof(s));for(int i=2;i<=n;i++){if(num[i]>=p){int m=num[i]-p+1;for(int j=1;j<=m;j++) {sum2+=v[i][j].value;s[v[i][j].pos]=1;}sum1+=m;}}if(sum1>l)continue;int m2=l-sum1;int cot=0;for(int i=2;i<=n;i++){if(cot>=m2)break;if(!s[c[i].pos]&&f[c[i].pos]!=1){ sum2+=c[i].value;cot++;}}ans=min(ans,sum2);}printf("%dn",ans);}return 0;
}