Robber on Tree!
You are given a rooted tree of N nodes, numbered 1 to N, with root as 1. Each node in the tree has some number of coins denoted by Ci representing the number of coins the ith node has.
At time t = 0, you are at the root node and there's a robber at one of the leaf nodes R. At each step, both you and robber take one step each and move to an adjacent node.
To prevent chaos, there's some restriction on both your and robber's movement. You have to choose a leaf node and take the shortest path to that leaf node and stop once you reach that leaf node. The robber has to take the shortest path to the root node and stop once the robber reaches the root node.
A person reaching a node first gets to take all the coins in the node leaving it empty for anyone who visits it after that time. If 2 people reach the node at the same time, they each get half of the coins in that node.
What's the maximum number of coins that you can aim to get in this process?
2<= N <= 100,000
-10000 <= Ci <= 10000
The number of coins in each node is even.
Input format:
First line contains two integers N, R representing the number of nodes in the tree and the position of the robber at t = 0.
Next N-1 lines contain two integers A, B denoting that there's an Undirected edge between nodes A and B.
The next line contains N space separated integers which represent the coins in each node.
Output Format:
The maximum no. of coins you can get.
Sample Input:
7 7
1 2
1 3
2 4
2 5
3 6
3 7
2 4 6 2 2 6 8
Sample Output:
11
#define int int64_t
int ans=INT_MIN;
bool dfs(int src,int par,int target,int t,vector<int> graph[],vector<int>& timeTaken)
{
if(src==target){
timeTaken[src]=t;
return true;
}
for(auto c:graph[src]){
if(src!=par){
if(dfs(c,src,target,t+1,graph,timeTaken)){
timeTaken[c]=t+1;
return true;
}
}
}
return false;
}
void dfs2(int src,int par,int t,int sum,vector<int> graph[],vector<int>& timeTaken,vector<int>& coins)
{
if(t<timeTaken[src]){
sum+=coins[src];
}
if(t==timeTaken[src]){
sum+=(coins[src]/2);
}
// cout<<src<<' ';
int child=0;
for(auto c:graph[src]){
if(par!=c){
child++;
dfs2(c,src,t+1,sum,graph,timeTaken,coins);
}
}
if(child==0){
ans=max(ans,sum);
}
return ;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int mod=998244353;
int n;
cin>>n;
int R;
cin>>R;
vector<int> graph[n+1];
for(int i=0;i<n-1;i++){
int a,b;
cin>>a>>b;
graph[a].push_back(b);
graph[b].push_back(a);
}
vector<int> coins(n+1);
for(int i=1;i<=n;i++)cin>>coins[i];
vector<int> timeTaken(n+1,INT_MAX);
timeTaken[R]=0;
dfs(R,-1,1,0,graph,timeTaken);
dfs2(1,-1,0,0,graph,timeTaken,coins);
cout<<ans<<endl;
return 0;
}