**PROBLEM LINK:**

Contest

Practice

*Author-*imranasuman

**DIFFICULTY:**

MEDIUM

**PREREQUISITES:**

DFS, Game Theory

**PROBLEM:**

There are two kings George and Alex playing a game on tree. There is a genie who can collect gold coin from nodes of the tree. Initially, the genie is at **i**th node. Starting from king George, they played alternate turns. In each turn, genie brought a gold coin for current king and then that king send the genie to one of the adjacent node of **i** (say **j**). The king who doesn’t receive coin from genie, looses the game. Your task is to guess the starting nodes from where the genie should start such that king George wins.

**EXPLANATION:**

Suppose that initially genie is at node **t**. Let **t** be the root of the tree.

For each node **v**, we define **state(v)** as follows:

Consider a subtree rooted at **v**. The two kings play the game using this subtree (they are

not allowed to move the genie out of the subtree), and initially the genie is at vertex **v**. If the

king George can win in this game, define **state(v)** = **W**. Otherwise **state(v)** = **L**.

Note that **state (t)** gives the result of the entire game when the genie is initially at **t**.

We claim the following:

- If there exists a child
**u**of**v**such that**Au < Av**and**state(u) = L**, then**state(v) = W**. - Otherwise,
**state(v) = L**. (In particular, if**v**is a leaf,**state(v) = L**.)

**Proof of 1:** Suppose that this is George’s turn and the genie is currently at **v**. First George

receive a coin from **v** (this is possible because **Av** is not zero) and send the genie to **u**. Whenever the Alex tries to send the genie from **u** to **v**, George can refuse to do that by sending him back to **u** (this is possible because **Av > Au**). This way, Alex is forced to play the game within the subtree rooted at **u**. Since **state(u) = L**, Alex loses and George wins. (Strictly speaking, Alex can also reduce the value of **Au** by sending the genie between **u** and **v** back and forth, but this doesn’t change the state of vertex u.)

**Proof of 2:** If **v** is a leaf, George can’t send the genie to any where and George lose. Otherwise he can send the genie from **v** to one of **v**’s children, **w**. There are two cases: **state(w) = W** or **Aw ≥ Av**. If **state(w) = W**, Alex never sends the genie back to **v** and play the rest of the game completely within the subtree rooted at **w**. Since **state(w) = W**, this way Alex wins and George lose. If **Aw ≥ Av**, Alex refuses to send the genie from **v** to **u** by sending genie back to **v** (this is possible because **Aw ≥ Av**). Thus, George lose in this case.

This way, for a fixed initial position of the genie, we can solve the problem in **O(N)**. In

total the complexity of this solution is **O(N^2)**.

**SOLUTIONS:**

## Author

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

void dfs(ll nd, ll par, vector<vector> &adj, vector &a, vector &f) {

f[nd] = false;

for (ll v: adj[nd]) {

if (v == par)

continue;

dfs(v, nd, adj, a, f);

if (!f[v] && a[nd] > a[v]) {

f[nd] = true;

}

}

}

void solve(int tc) {

ll n, i, j, k, l, x, y;

cin >> n;

vector<vector> adj(n + 5);

vector a(n + 5, 0);

vector f(n + 5, false);

for (i = 1; i < n; i++) {

cin >> x >> y;

adj[x].push_back(y);

adj[y].push_back(x);

}

for (i = 1; i <= n; i++) {

cin >> a[i];

}

```
vector<ll> ans;
for (i = 1; i <= n; i++) {
dfs(i, 0, adj, a, f);
if (f[i]) {
ans.push_back(i);
}
}
cout << (ll) ans.size() << "\n";
for (i = 0; i < (ll) ans.size(); i++) {
cout << ans[i] << " ";
}
cout << "\n";
```

}

bool imp = true;

int main() {

fio;

int t = 1;

if (imp)cin >> t;

int m = t;

while (t–) {

solve(m - t);

}

return 0;

}