Submission #8805942

---

Source Code Expand

#include <bits/stdc++.h>
#define root 1, n, 1, pre[top[u]], pre[u]
#define ls l, mid, k << 1
#define rs mid + 1, r, k << 1 | 1
#define L k << 1
#define R k << 1 | 1
using namespace std;
int read();

int n;
vector<int> e[200005];
void add(int f, int t) { e[f].push_back(t), e[t].push_back(f); }
int fa[200005], dep[200005], sn[200005], sz[200005];

void dfs1(int u) {
	sz[u] = 1;
    for (vector<int>::iterator v = e[u].begin(); v != e[u].end(); v++)
        if ((*v) != fa[u]) {
			dep[*v] = dep[u] + 1, fa[*v] = u, dfs1(*v);
			sz[u] += sz[*v], sn[u] = sz[sn[u]] < sz[*v] ? *v : sn[u];
		}
}

int pre[200005], top[200005], dfn;
void dfs2(int u) {
	pre[u] = ++dfn;
	if (!sn[u]) return;
	top[sn[u]] = top[u], dfs2(sn[u]);
    for (vector<int>::iterator v = e[u].begin(); v != e[u].end(); v++)
		if ((*v) != fa[u] && (*v) != sn[u]) top[*v] = *v, dfs2(*v);
}

queue<int> q;

struct Seg {
	int mn[200005], xsum[200005];
	int tag1[200005], tag2[200005];
	void Tag1(int k, int v) { mn[k] += v, tag1[k] += v; }
	void Tag2(int k, int v) { xsum[k] ^= v, tag2[k] ^= v; }
	void psd1(int k) { Tag1(L, tag1[k]), Tag1(R, tag1[k]), tag1[k] = 0;	}
	void psd2(int k) { Tag2(L, tag2[k]), Tag2(R, tag2[k]), tag2[k] = 0; }
	void mdi1(int l, int r, int k, int st, int en, int v) {
		if (st > r || en < l) return;
		if (st <= l && en >= r) return Tag1(k, v);
		psd1(k);
		int mid = l + r >> 1;
		mdi1(ls, st, en, v), mdi1(rs, st, en, v), mn[k] = min(mn[L], mn[R]);
	}

	void mdi2(int l, int r, int k, int st, int en, int v) {
		if (st > r || en < l) return;
		if (st <= l && en >= r) return Tag2(k, v);
		psd2(k);
		int mid = l + r >> 1;
		mdi2(ls, st, en, v), mdi2(rs, st, en, v);
	}

	void work(int l, int r, int k) {
		if (l == r)	return mn[k] = 1000000000, q.push(xsum[k]);
		int mid = l + r >> 1;
		psd1(k), psd2(k);
		if (mn[L] == 1) work(ls);
		if (mn[R] == 1) work(rs);
		mn[k] = min(mn[L], mn[R]);
	}
} seg;

void modi(int u, int v, int val, int id) {
	while (top[u] != top[v]) {
		if (dep[top[u]] < dep[top[v]]) swap(u, v);
		seg.mdi1(root, val), seg.mdi2(root, id), u = fa[top[u]];
	}
	if (dep[u] > dep[v]) swap(u, v);
	seg.mdi1(1, n, 1, pre[u] + 1, pre[v], val);
	seg.mdi2(1, n, 1, pre[u] + 1, pre[v], id);
}

struct E {
	int u, v;
	void init(int i) { modi(u = read(), v = read(), 1, i); }
} p[200005];

int main() {
    n = read();
    for (int i = 1; i < n; ++i) add(read(), read());
    dep[1] = 1, dfs1(1), top[1] = 1, dfs2(1);
    for (int i = 1, u, v; i < n; ++i) p[i].init(i);
	seg.mdi1(1, n, 1, 1, 1, 100000000),	seg.work(1, n, 1);
	int cnt = 0;
	while (!q.empty()) {
		int t = q.front();
		q.pop(), cnt++, modi(p[t].u, p[t].v, -1, t), seg.work(1, n, 1);
	}
    puts(cnt == n - 1 ? "YES" : "NO");
    return 0;
}

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') f = (c == '-') ? -1 : f, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

Submission Info

Judge Result