TWKNGS Editorial

editorial
, , ,
1

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 ith 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:

  1. If there exists a child u of v such that Au < Av and state(u) = L, then state(v) = W.
  2. 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;
}

1 Like