0 like 0 dislike
2,306 views

| 2,306 views

0 like 0 dislike

The solution involes game theory + dynamic programming on tree .

Code(C++) :

```//Author : Kumar K
#include <bits/stdc++.h>

using namespace std;
typedef long long int ll ;
vector <ll> G[200000];
ll alice[200000];
ll bob[100005];
ll parent[200005];
vector <ll> used(100005,0);
struct hash_pair {
template <class T1, class T2>
size_t operator()(const pair<T1, T2>& p) const
{
auto hash1 = hash<T1>{}(p.first);
auto hash2 = hash<T2>{}(p.second);

if (hash1 != hash2) {
return hash1 ^ hash2;
}

// If hash1 == hash2, their XOR is zero.
return hash1;
}
};

unordered_map<pair<ll, ll>, ll, hash_pair> um;

void dfs(ll node){
used[node] = 1 ;
// cout<<node<<" ";
for(auto u : G[node]){
if(used[u]==0){
parent[u] = node ;
dfs(u);
}
}
ll ww = 0 ; ll qq = 1e18 ;
ll ans = 0 ;
for(auto children : G[node]){

if(children!=parent[node]){
ww = max(ww,um[{children,node}] + bob[children]) ;
qq = min(qq,-1*um[{children,node}] + alice[children]) ;
}
}
alice[node] = ww ;
if(qq==1e18){
bob[node] = 0 ;
}
else
{
bob[node] = qq ;
}
//cout<<node<<" "<<alice[node]<<" "<<bob[node];cout<<endl;
}

int main() {
int N ;
cin>>N ;
int i = 1 ; parent[i] = -1;
while(i<=N-1){
int x,y,z ;
cin>>x>>y>>z ;
G[x].push_back(y);
G[y].push_back(x);
um[{x,y}] = z;
um[{y,x}] = z ;
i++;
}
dfs(1);
cout<<alice[1];
return 0;
}```

Input :

1 2 9
1 3 5
3 4 5
3 5 4
6 2 3

Output : 6

by Expert (109,630 points)
edited