Cerinta completa

Alice and Bob are playing a game, defined below:

  • There is an undirected tree graph with nodes that has the following properties:
    • Each node has golden coins.
    • Node is root of the tree.
    • The parent node of some node is defined as .
  • Moves
    • Players move in turns.
    • During a move, a player can select a node and move one or more coins to .
    • If the current player can’t make any move, they lose the game.

The game quickly becomes boring because the result is determined by the tree’s configuration and the number of coins in each node (assuming that both players play optimally).

Alice decides to instead challenge Bob by asking him questions. For each question :

  1. Alice picks a node and removes the edge between and .
  2. She picks another node and draws a new undirected edge between and . So now .

Bob must determine if the first player has a winning strategy for the new tree or not. It’s possible that after Alice draws the new edge, the graph will no longer be a tree; if that happens, the question is invalid. Each question is independent, so the answer depends on the initial state of the graph (and not on previous questions).

Given the tree and the number of coins in each node, can you help Bob answer all questions?

Input Format

The first line contains an integer, (the number of nodes).
The second line contains space-separated integers, , describing the number of coins in each node.
Each of the subsequent lines contains space-separated integers denoting an undirected edge between nodes and , respectively.
The next line contains an integer, (the number of questions Alice asks).
Each of the subsequent lines contains space-separated integers, and , respectively.

Constraints

For each question:

Output Format

On a new line for each question, print if the first player has a winning strategy, print if they do not, or print if the question is not valid.

Sample Input

6
0 2 2 1 3 2
1 2
1 3
3 4
3 5
4 6
3
6 2
4 1
3 6

Sample Output

NO
YES
INVALID

Explanation

Initally the tree looks like this:

After the first question (), the tree looks like this:

Alice removes the edge conecting node to and makes the new parent node of . Because this configuration does not result in a winning strategy, we print on a new line.

After the second question (), the tree looks like this:

Alice removes the edge conecting node to and makes the new parent node of . Because this configuration results in a winning strategy, we print on a new line.

After the third question (), the graph is no longer a tree:

Alice removes the edge conecting node to and makes the new parent node of . The graph is now partitioned into two separate subgraphs (one of which is also not a tree); because the game must be played on a single undirected tree graph, we print on a new line.

Limbajul de programare folosit: cpp14

Cod:

#include<bits/stdc++.h>

using namespace std;
#define MAXN 50000

int N;
long long coin[MAXN];
long long MOVE[MAXN];
long long odd[MAXN];
long long even[MAXN];
long long level[MAXN];
long long flag[MAXN];
long long parent[MAXN][20];

vector<int> AdjList[MAXN];

bool no_cycle(int p, int q){

	if (level[p] < level[q])
		swap(p, q);
	else
		return true;

	int log;
	for (log = 1; 1 << log <= level[p]; log++);
		log--;

	for (int i = log; i >= 0; i--)
		if (level[p] - (1 << i) >= level[q])
			p = parent[p][i];
			
	if ( p == q )
		return false;
	else
		return true;
}

void rec(int v, int l, int f){
	flag[v] = true;
	parent[v][0] = f;

	level[v] = l;
	MOVE[v] = 0;

	odd[v] = 0;
	even[v] = coin[v];
	for (size_t i=0; i<AdjList[v].size(); i++)
		if ( !flag[AdjList[v][i]] ) {
			rec(AdjList[v][i], l + 1, v);
			odd[v]  ^= even[AdjList[v][i]];
			even[v] ^= odd[AdjList[v][i]];
		}
}

void init(){
	cin >> N;

	memset(flag, 0, sizeof(flag));
	for (int i=0; i<N; i++)
		cin >> coin[i];
	
	for (int i=0; i<N-1; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		AdjList[a].push_back(b);
		AdjList[b].push_back(a);
	}
	
	for (int i=0; i<MAXN; i++)
		for (int j=0; j<20; j++)
			parent[i][j] = -1;

	rec(0, 0, -1);
	
	for (int j = 1; 1 << j < N; j++)
         for (int i = 0; i < N; i++)
             if (parent[i][j - 1] != -1)
                 parent[i][j] = parent[parent[i][j - 1]][j - 1];
}

void solve(){
	int q;
	cin >> q;

	while(q--){
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		if ( no_cycle(u, v) ) {
			long long s = odd[0];
			
			if ( level[u] % 2 == 1)
				s = s ^ even[u];
			else
				s = s ^ odd[u];

			
			if ( (level[v] + 1) % 2 == 1 )
				s = s ^ even[u];
			else
				s = s ^ odd[u];

			if ( s != 0 )
				cout << "YES" << endl;
			else
				cout << "NO" << endl;
		} else
			cout << "INVALID" << endl;
	}
}

int main(){
	init();
	solve();
}

Scor obtinut: 1.0

Submission ID: 464647922

Link challenge: https://www.hackerrank.com/challenges/move-the-coins/problem

Move the Coins