编程介的小学生 2018-12-05 11:02 采纳率: 18.6%
浏览 313
已采纳

求问一下,这个问题的正确的编程方法是什么?怎么C语言的解决?

Problem Description
Professor Zhang has a rooted tree, whose vertices are conveniently labeled by 1,2,...,n. And the i-th vertex is assigned with weight wi.

For each s∈{1,2,...,n}, Professor Zhang wants find a sequence of vertices v1,v2,...,vm such that:

  1. v1=s and vi is the ancestor of vi−1 (1<i≤m).
  2. the value f(s)=wv1+∑i=2mwvi opt wvi−1 is maximum. Operation x opt y denotes bitwise AND, OR or XOR operation of two numbers.

Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains an integer n and a string opt (2≤n≤216,opt∈{AND,OR,XOR}) -- the number of vertices and the operation. The second line contains n integers w1,w2,...,wn (0≤wi<216). The thrid line contain n−1 integers f2,f3,...,fn (1≤fi<i), where fi is the father of vertex i.

There are about 300 test cases and the sum of n in all the test cases is no more than 106.

Output
For each test case, output an integer S=(∑i=1ni⋅f(i)) mod (109+7).

Sample Input
3
5 AND
5 4 3 2 1
1 2 2 4
5 XOR
5 4 3 2 1
1 2 2 4
5 OR
5 4 3 2 1
1 2 2 4

Sample Output
91
139
195

  • 写回答

1条回答 默认 最新

  • threenewbee 2019-03-28 12:23
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

    报告相同问题?

    悬赏问题

    • ¥20 C语言字符串不区分大小写字典排序相关问题
    • ¥15 关于#python#的问题:我希望通过逆向技术爬取1688搜索页下滑加载的数据
    • ¥15 学习C++过程中遇到的问题
    • ¥15 关于Linux的终端里,模拟实现一个带口令保护的屏保程序遇到的输入输出的问题!(语言-c语言)
    • ¥15 学习C++过程中遇到的问题
    • ¥15 请问,这个嵌入式Linux系统怎么分析,crc检验区域在哪
    • ¥15 二分类改为多分类问题
    • ¥15 Unity微信小游戏上调用ReadPixels()方法报错
    • ¥15 如何通过求后验分布求得样本中属于两种物种其中一种的概率?
    • ¥15 q从常量变成sin函数,怎么改写python代码?