Cerinta completa

Given a tree with vertices numbered from to . You need to process queries. Each query represents a vertex number encoded in the following way:

Queries are encoded in the following way: Let, be the query and be the answer for the query where and is always . Then vertex .
We are assure that is between and , and hasn’t been removed before.

Note: is the bitwise XOR operator.

For each query, first decode the vertex and then perform the following:

  1. Print the size of the connected component containing .
  2. Remove vertex and all edges connected to .

Input Format

The first line contains a single integer, , denoting the number of vertices in the tree.
Each line of the subsequent lines (where ) contains space-separated integers describing the respective nodes, and , connected by edge .
The next line contains a single integer, , denoting the number of queries.
Each line of the subsequent lines contains a single integer, vertex number .

Constraints

Output Format

For each query, print the size of the corresponding connected component on a new line.

Sample Input 0

3
1 2
1 3
3
1
1
2

Sample Output 0

3
1
1

Sample Input 1

4
1 2
1 3
1 4
4
3
6
2
6

Sample Output 1

4
3
2
1

Explanation

Sample Case 0:
We have, = 0 and connected component :
has vertex = = = . The size of connected component containing is .
So, = .
Removing vertex and all of it’s edges, we get two disconnected components :
has vertex = = = . The size of connected component containing is .
So, = .
Removing vertex and all of it’s edges, we are left with only one component :
has vertex = = = . The size of connected component containing is .
So, = .
Removed vertex .

Sample Case 1:
We have, = and connected component :
has vertex = = = . The size of connected component containing is .
So, = .
Removing vertex and all of it’s edges, we get component :
has vertex = = = . The size of connected component containing is .
So, = .
Removing vertex and all of it’s edges, now, we get two disconnected components :
has vertex = = = . The size of connected component containing is .
So, = .
Removing vertex and all of it’s edges, now we are left with only one component :
has vertex = = = . The size of connected component containing is .
So, = .
Removed vertex .

Limbajul de programare folosit: cpp14

Cod:

#include <bits/stdc++.h>
using namespace std;

struct node {
	int size = 1;
	node *lch = nullptr;
	node *rch = nullptr;
	node *parent = nullptr;
};

unsigned xor32() {
	static unsigned z = time(NULL);
	z ^= z << 13; z ^= z >> 17; z ^= z << 5;
	return z;
}
int size(node *x) {
	return x == nullptr ? 0 : x->size;
}
node *push(node *x) {
	x->size = 1 + size(x->lch) + size(x->rch);
	x->parent = nullptr;
	if (x->lch != nullptr) x->lch->parent = x;
	if (x->rch != nullptr) x->rch->parent = x;
	return x;
}
node *merge(node *x, node *y) {
	if (x == nullptr) return y;
	if (y == nullptr) return x;
	if (xor32() % (size(x) + size(y)) < size(x)) {
		x = push(x);
		x->rch = merge(x->rch, y);
		return push(x);
	} else {
		y = push(y);
		y->lch = merge(x, y->lch);
		return push(y);
	}
}
pair<node *, node *> split(node *x, int k) {
	if (x == nullptr) return{ nullptr, nullptr };
	x = push(x);
	if (size(x->lch) >= k) {
		auto p = split(x->lch, k);
		x->lch = p.second;
		return{ p.first, push(x) };
	} else {
		auto p = split(x->rch, k - size(x->lch) - 1);
		x->rch = p.first;
		return{ push(x), p.second };
	}
}
node *root(node *x) {
	if (x->parent == nullptr) return x;
	return root(x->parent);
}
int index_of(node *x) {
	int result = -1;
	bool l = true;
	while (x != nullptr) {
		if (l) result += 1 + size(x->lch);
		if (x->parent == nullptr) break;
		l = x->parent->rch == x;
		x = x->parent;
	}
	return result;
}

vector<int> g[200200];
int depth[200200];
node *L[200200];
node *R[200200];

node *tr = nullptr;

void dfs(int curr, int prev) {
	L[curr] = new node();
	tr = merge(tr, L[curr]);
	for (int next : g[curr]) if (next != prev) {
		depth[next] = depth[curr] + 1;
		dfs(next, curr);
	}
	R[curr] = new node();
	tr = merge(tr, R[curr]);
}

void cut(int u, int v) {
	if (depth[u] < depth[v]) swap(u, v);

	int l = index_of(L[u]);
	int r = index_of(R[u]);

	node *rt = root(L[u]);
	auto x = split(rt, r + 1);
	auto y = split(x.first, l);
	merge(y.first, x.second);
}

int main() {
	int n;
	cin >> n;

	for (int i = 0; i < n - 1; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		u--; v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	int m;
	cin >> m;

	dfs(0, -1);

	int ans = 0;
	for (int i = 0; i < m; i++) {
		int x;
		scanf("%d", &x);
		int v = (ans ^ x) - 1;
		ans = size(root(L[v])) / 2;
		for (int u : g[v]) cut(u, v);
		printf("%d\n", ans);
	}
}

Scor obtinut: 1.0

Submission ID: 464647368

Link challenge: https://www.hackerrank.com/challenges/tree-splitting/problem

Tree Splitting