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 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 cicandies 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 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: fi (1 ≤ fi ≤ nfi ≠ 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.

枚举孩子赢的选举得到的票数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("%d\n",ans);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏進无尽的文章

Swift| 基础语法(四)

总结下 swift下的基础语法,里面涉及到:常量&变量、Swift中的数据类型、逻辑分支、循环、字符串相关、数组和字典、方法的书写调用等内容,考虑到阅读体验分多...

17510
来自专栏Code_iOS

Objective-c 知识总结 -- 继承

观察发现,它们属性和方法声明是相同的,都有 填充色(fillcolor)、尺寸+位置(bounds)、绘制方法;

13210
来自专栏Felix的技术分享

霍夫曼压缩算法

36580
来自专栏源哥的专栏

找到java代码中没有被使用的公用方法

最近,我打算对我们项目的代码进行清理,准备把一些没有被使用到的公用方法清理掉,但是我在网络找了一遍,像PMD,Findbugs等静态工具,都只能找到没有被使用的...

19010
来自专栏Hongten

python开发_python代码风格(coding style)

13210
来自专栏cmazxiaoma的架构师之路

你应该会的一道多线程笔试题

30930
来自专栏Google Dart

Dart语言指南(一) 顶

此文着重展示如何使用Dart语言的每一个主要功能,从变量和操作符到类和库,假设您已经知道如何用另一种编程语言。

16020
来自专栏偏前端工程师的驿站

Java魔法堂:深入正则表达式API

目录                               一、前言 二、正则表达式的使用诉求 三、java.util.regex包 四、java.lan...

21350
来自专栏微信公众号:Java团长

Java集合类型详解

这篇文章总结了所有的Java集合(Collection)。主要介绍各个集合的特性和用途,以及在不同的集合类型之间转换的方式。

16920
来自专栏机器学习与自然语言处理

04-树6. Huffman Codes--优先队列(堆)在哈夫曼树与哈夫曼编码上的应用

题目来源:http://www.patest.cn/contests/mooc-ds/04-%E6%A0%916 In 1953, David A. Huffm...

28970

扫码关注云+社区

领取腾讯云代金券