Submission #1610771

---

Source Code Expand

#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;

#define iter(i, n) for (int i = 1; i <= n; ++i)

#define NR 101000

const int inf = 1e9;

vector<int> g[NR], add[NR << 2], del[NR << 2];
int n, bg[NR], sz[NR], son[NR], dsz, ex[NR], ey[NR], fa[NR], top[NR], dep[NR];
int t[NR << 2];
bool vis[NR];

#define lx x << 1
#define rx x << 1 | 1
#define RT 1, 1, n
#define SL lx, l, mid
#define SR rx, mid + 1, r

void upd(int x) {
	t[x] = min(t[lx], t[rx]) + add[x].size() - del[x].size();
//	printf("!%d %d\n", x, t[x]);
}

void seg_modify(int x, int l, int r, int ml, int mr, int tag, int d) {
	if (ml <= l && r <= mr) { d == +1 ? add[x].push_back(tag) : del[x].push_back(tag); t[x] += d; return; }

	int mid = (l + r) / 2;
	if (ml <= mid) seg_modify(SL, ml, mr, tag, d);
	if (mr > mid) seg_modify(SR, ml, mr, tag, d);
	upd(x);
}

#define fx top[x]
#define fy top[y]

void modify(int x, int y, int tag, int d) {
	while (fx != fy) {
		if (dep[fx] < dep[fy]) swap(x, y);
		seg_modify(RT, bg[fx], bg[x], tag, d); x = fa[fx];
	}
	if (dep[x] > dep[y]) swap(x, y);
	if (x != y) seg_modify(RT, bg[x] + 1, bg[y], tag, d);
}

void dfs(int x) {
	sz[x] = 1, son[x] = 0;
	for (int v : g[x]) if (v != fa[x]) {
		dep[v] = dep[x] + 1, fa[v] = x, dfs(v), sz[x] += sz[v];
		if (sz[v] > sz[son[x]]) son[x] = v;
	}
}

void bt(int x, int tp) {
	top[x] = tp; bg[x] = ++dsz;
	if (son[x] != 0) bt(son[x], tp);
	for (int v : g[x]) if (v != fa[x] && v != son[x]) bt(v, v);
}

void seg_clr(int x, int l, int r) {
	if (l == r) { t[x] = 2 * inf; return; }
	int mid = (l + r) / 2;
	if (t[lx] < t[rx]) seg_clr(SL);
	else seg_clr(SR);
	upd(x);
}

int seg_min(int x, int l, int r) {
	int res = -1;
	if (add[x].size() == del[x].size()) add[x].clear(), del[x].clear();
	else if (add[x].size() == del[x].size() + 1) {
		for (int i : del[x]) vis[i] = true;
		for (int i : add[x]) if (!vis[i]) res = i;
		for (int i : del[x]) vis[i] = false;	
		
		del[x].clear();
		add[x].clear();
		
		add[x].push_back(res);
	} else assert(0);

	if (res != -1) return res;
	assert(l != r);
	int mid = (l + r) / 2;

	if (t[lx] < t[rx]) return seg_min(SL);
	else return seg_min(SR);
}

int main() {
	scanf("%d", &n);

	iter(i, n - 1) {
		int x, y;
		scanf("%d%d", &x, &y);
		g[x].push_back(y), g[y].push_back(x);
	}

	dfs(1); bt(1, 1);

	iter(i, n) {
		scanf("%d%d", &ex[i], &ey[i]);
		modify(ex[i], ey[i], i, +1);
	}

	

	while (t[1] < inf) {
		//printf("!%d\n", t[1]);
		if (t[1] > 1) { puts("NO"); return 0; }
		if (t[1] == 1) {
			int i = seg_min(RT);
			seg_clr(RT);
			modify(ex[i], ey[i], i, -1);
		} else seg_clr(RT);
	}

	puts("YES");
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:95:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:99:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
                        ^
./Main.cpp:106:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &ex[i], &ey[i]);
                                ^

Judge Result