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

求问一下,这个问题的正确的编程方法是什么?怎么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
    最佳回答
    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题