題干：

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?ith?kid will vote for his best friend?fi?(where 1?≤ fi?≤ n, and it's too shame to vote for yourself, so?fi?≠ 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?ci?candies to the?ith?kid, the?ith?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 wants?EXCEPT?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:?fi?(1?≤ fi?≤ n,?fi?≠ i, and 2?≤ i ≤ n) -- represents that the best friend of?ith?kid is indexed with?fi.

The third line contains?n-1?integers:?ci?(1?≤ ci?≤?1000, and 2?≤ i ≤ n) -- represents that if Sheldon gave?ci?candies to the?ith?kid, the?ith?kid would vote Sheldon, instead of their old best friend?fi, 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 2nd?kid, the 2nd?kid and Sheldon will both have 2 votes. In this case, Sheldon have to pay 100 candies to the 4th?kid, and get 3 votes to win;
• If Sheldon vote for 3rd?or 4th?kid, Sheldon will win with 2 votes without sacrifice any candy.

題目大意：

在學期開始的幼兒園，n個小孩（1到n）在課堂上需要選擇他們的新領導。
第一個孩子會投票給他最好的朋友fi（其中1≤fi≤n，這太可惜了，自己投票，所以fi≠i）。?

獲得最多票數的孩子將是領袖。 如果有一個以上的孩子獲得最多的票數，在新學期將有多個領導人。

小謝爾頓（下標為1）想成為唯一的領導者。 （這意味著他得到的票數應該嚴格大于任何其他。）

如果他給ci糖果給第i個孩子，第i個孩子會認為謝爾頓作為新的最好的朋友，當然投票謝爾頓。

請幫助謝爾頓成為唯一的領導者，最低的糖果成本。 順便說一下，謝爾頓應該投票支持自己想要的任何一個人。

解題報告：

如果1號選手已經指定投票給哪一位選手，那很顯然和codeforce上的那個C題Elections一模一樣，n^2就可以解決。但是這題既然數據范圍是100，說明肯定有坑，我本來的想法是先不讓1號選手投票，最后再讓他直接投給最小的那個人，但是發現這樣好像不太行，所以干脆就直接枚舉他投票給哪一個人就可以了。這樣復雜度O(n^3)，，反正也說得過去。就這么xjb寫了，，剛開始wa了無數發還以為思路有問題，，結果發現寫了cmp函數但是忘了sort了、、、

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; int n; int bk[105]; struct Node {int f,c; } p[MAX]; bool cmp(Node a,Node b) {return a.c < b.c; } int cnt[105]; int main() {int t;cin>>t;while(t--) {scanf("%d",&n);memset(cnt,0,sizeof cnt);for(int i = 2; i<=n; i++) scanf("%d",&p[i].f);for(int i = 2; i<=n; i++) scanf("%d",&p[i].c);int ans = 0x3f3f3f3f;for(int i = 2; i<=n; i++) cnt[p[i].f]++;sort(p+2,p+n+1,cmp);for(int qq = 2; qq<=n; qq++) {p[1].f = qq;for(int piao = 1; piao <= n; piao++) {memset(cnt,0,sizeof cnt);memset(bk,0,sizeof bk);for(int i = 1; i<=n; i++) cnt[p[i].f]++;int chu = cnt[1];int cost = 0;for(int i = 2; i<=n; i++) {if(p[i].f != 1 && cnt[p[i].f ] >= piao) {cost += p[i].c;chu++;cnt[p[i].f]--;bk[i] = 1;}}for(int i = 2; i<=n; i++) {if(p[i].f !=1 && chu < piao && bk[i] == 0) {chu++;cost += p[i].c;}}ans = min(ans,cost);}}printf("%d\n",ans);}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【ZOJ - 3715】Kindergarten Election（枚举得票数，贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。