### godmodegod's blog

By godmodegod, 3 weeks ago,

You are given the following:

• A tree with N nodes
• An array A denoting the value of each node
• A non-negative integer K

You can do the following operation on the tree at most once:

1. Pick a node r and make it the root of the tree.
2. In the new tree, pick a node x, and for each node v in the subtree of x, update A[v] = A[v] XOR K.

Determine the maximum sum of values of all the nodes in the tree that can be obtained.

Notes

• 1-Based indexing.
• XOR denotes the Bitwise XOR operator.
• A subtree of a node contains all the nodes that are descendants of that node and the node itself.

Example

Assumptions

• N = 3
• edges = [(1, 2), (1, 3)]
• A = [1, 1, 3]
• K = 3

 » 3 weeks ago, # |   0 My solution Spoiler#define ll long long const int sz = 1e5+5; ll in[sz], out[sz],subsz[sz],ans=0,sum; void dfs1(ll node, ll par,vector adj[],int K,vector &A){ in[node] = (A[node-1]^K); subsz[node]=A[node-1]; for(auto child: adj[node]){ if(child == par)continue; dfs1(child,node,adj,K,A); in[node]+=in[child]; subsz[node]+=subsz[child]; } ans=max(ans,sum-subsz[node]+in[node]); } void dfs2(ll node, ll par,vector adj[],int K,vector &A){ ll mx1 = -1; ll mx2 = -1; for(auto child: adj[node]){ if(child == par) continue; dfs2(child,node,adj,K,A); ans=max(ans,in[1]-in[child]+subsz[child]); } } long long maximumSum(int N,vector> &edges,vector &A,int K){ ans=accumulate(A.begin(),A.end(),0ll); sum=ans; for(int i=0;i<=N;i++) { in[i]=0; out[i]=0; subsz[i]=0; } vector adj[N+1]; for(int i=0;i