Born Slippy

题目连接：

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

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

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

Hint

题意

给你一棵树，树上点有点权，对于每个点，你需要找到到根的那条链上的一个子序列。

使得f[i] = w[v[i]] + sigma w[v[i]] opt w[v[i+1]] 最大。

然后输出sigma(if[i])%mod

题解：

不会正解，n^2dp非常简单，很容易就能想到

然后感觉这道题的数据比较难造，就直接暴力了，然后一发就过了。

代码

#include
    
     using namespace std;const int maxn = 70000;const int mod = 1e9+7;long long dp[maxn],w[maxn];int n;vector
     
      E[maxn];string opt;set
      
       
         > S;set
        
         
           >::iterator it;long long solve(long long x,long long y){ if(opt=="XOR")return x^y; if(opt=="AND")return x&y; if(opt=="OR")return x|y;}void dfs(int x){ if(S.size()!=0){ int tot = 0; for(it = S.begin();it!=S.end()&&tot<100;it++,tot++){ dp[x] = max(dp[x],-(it->first)+solve(w[it->second],w[x])); } } S.insert(make_pair(-dp[x],x)); for(int i=0;i
          
           >opt; for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=2;i<=n;i++){ int a;scanf("%d",&a); E[a].push_back(i); } dfs(1); long long ans = 0; for(int i=1;i<=n;i++){ ans = (ans+i*(dp[i]%mod+w[i]%mod)) % mod; } printf("%I64d\n",ans);}int main(){ int t; scanf("%d",&t); while(t--)solve(); return 0;}