C++11(clang++ 3.9) 解法, 执行用时: 632ms, 内存消耗: 18788K, 提交时间: 2019-03-09 15:43:08

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
struct BinaryIndextree {
	int a[MAXN], n;
	int Log, bit[MAXN];
	void init(int x) {
		n = x; bit[Log = 0] = 1;
		while (bit[Log] * 2 <= n) {
			Log++;
			bit[Log] = bit[Log - 1] << 1;
		}
		memset(a, 0, sizeof(a));
	}
	void modify(int pos, int d) {
		for (int i = pos; i <= n; i += i & -i)
			a[i] += d;
	}
	int query(int l, int r) {
		int ans = 0;
		for (int i = r; i >= 1; i -= i & -i)
			ans += a[i];
		for (int i = l - 1; i >= 1; i -= i & -i)
			ans -= a[i];
		return ans;
	}
	int pred(int pos, int val) {
		if (val == 0) return 0;
		int ans = 0;
		for (int i = Log; i >= 0; i--)
			if (ans + bit[i] <= n && a[ans + bit[i]] < val) {
				ans += bit[i];
				val -= a[ans];
			}
		return ans + 1;
	}
} Size, Light;
struct SegmentTree {
	struct Node {
		int lc, rc;
		int Max;
	} a[MAXN * 2];
	int root, size, n;
	void build(int &root, int l, int r) {
		root = ++size;
		if (l == r) return;
		int mid = (l + r) / 2;
		build(a[root].lc, l, mid);
		build(a[root].rc, mid + 1, r);
	}
	void update(int root) {
		a[root].Max = max(a[a[root].lc].Max, a[a[root].rc].Max);
	}
	void init(int x) {
		n = x;
		size = root = 0;
		build(root, 1, n);
	}
	void modify(int root, int l, int r, int pos, int val) {
		if (l == r) {
			a[root].Max = val;
			return;
		}
		int mid = (l + r) / 2;
		if (mid >= pos) modify(a[root].lc, l, mid, pos, val);
		else modify(a[root].rc, mid + 1, r, pos, val);
		update(root);
	}
	void modify(int pos, int val) {
		modify(root, 1, n, pos, val);
	}
	int query(int root, int l, int r, int ql, int qr) {
		if (l == ql && r == qr) return a[root].Max;
		int mid = (l + r) / 2, ans = 0;
		if (mid >= ql) chkmax(ans, query(a[root].lc, l, mid, ql, min(mid, qr)));
		if (mid + 1 <= qr) chkmax(ans, query(a[root].rc, mid + 1, r, max(mid + 1, ql), qr));
		return ans;
	}
	int query(int l, int r) {
		return query(root, 1, n, l, r);
	}
} ST;
struct Node {
	int lc, rc;
	int father;
	int dfn, rit;
	int up, size;
} a[MAXN];
int n, q, timer, pos[MAXN], home[MAXN];
long long ans[MAXN], curr;
bool vis[MAXN], intree[MAXN];
void renew(int pos) {
	int size = Size.query(a[pos].dfn, a[pos].rit);
	int f = a[pos].father;
	if (a[f].lc == pos) {
		int tmp = a[f].rc, tsize = Size.query(a[tmp].dfn, a[tmp].rit);
		if (!intree[tmp] || size > tsize) {
			Light.modify(a[pos].dfn, -1);
			if (intree[tmp]) Light.modify(a[tmp].dfn, 1);
			curr += pos;
			if (intree[tmp]) curr -= tmp;
		} else if (size == tsize) {
			int nxtp = ST.query(a[pos].dfn, a[pos].rit);
			int nxtt = ST.query(a[tmp].dfn, a[tmp].rit);
			if (nxtp >= nxtt) {
				Light.modify(a[pos].dfn, -1);
				Light.modify(a[tmp].dfn, 1);
				curr += pos;
				curr -= tmp;
			}
		}
	} else {
		int tmp = a[f].lc, tsize = Size.query(a[tmp].dfn, a[tmp].rit);
		if (!intree[tmp] || size > tsize) {
			Light.modify(a[pos].dfn, -1);
			if (intree[tmp]) Light.modify(a[tmp].dfn, 1);
			curr += pos;
			if (intree[tmp]) curr -= tmp;
		} else if (size == tsize) {
			int nxtp = ST.query(a[pos].dfn, a[pos].rit);
			int nxtt = ST.query(a[tmp].dfn, a[tmp].rit);
			if (nxtp > nxtt) {
				Light.modify(a[pos].dfn, -1);
				Light.modify(a[tmp].dfn, 1);
				curr += pos;
				curr -= tmp;
			}
		}
	}
} 
void work(int pos, int up) {
	a[pos].up = up;
	a[pos].dfn = ++timer;
	if (a[pos].lc == 0 && a[pos].rc != 0) work(a[pos].rc, up);
	if (a[pos].rc == 0 && a[pos].lc != 0) work(a[pos].lc, up);
	if (a[pos].lc != 0 && a[pos].rc != 0) {
		if (a[a[pos].lc].size >= a[a[pos].rc].size) {
			work(a[pos].lc, up);
			work(a[pos].rc, a[pos].rc);
		} else {
			work(a[pos].rc, up);
			work(a[pos].lc, a[pos].lc);
		}
	}
	a[pos].rit = timer;
}
void dfs(int pos) {
	a[pos].size = 1;
	if (a[pos].lc) {
		dfs(a[pos].lc);
		a[pos].size += a[a[pos].lc].size;
	}
	if (a[pos].rc) {
		dfs(a[pos].rc);
		a[pos].size += a[a[pos].rc].size;
	}
}
int main() {
	read(n);
	for (int i = 1; i <= n; i++) {
		read(a[i].lc), read(a[i].rc);
		if (a[i].lc != 0) a[a[i].lc].father = i;
		if (a[i].rc != 0) a[a[i].rc].father = i;
	}
	dfs(1);
	work(1, 1);
	ST.init(n);
	Size.init(n);
	Light.init(n);
	for (int i = 1; i <= n; i++)
		home[a[i].dfn] = i;
	read(q);
	for (int i = 1; i <= q; i++) {
		read(pos[i]);
		vis[pos[i]] = true;
	}
	int point = q;
	for (int i = n; i >= 2; i--)
		if (!vis[home[i]]) pos[++point] = home[i];
	Size.modify(a[1].dfn, 1);
	intree[1] = true;
	for (int i = 1; i <= point; i++)
		ST.modify(a[pos[i]].dfn, i);
	for (int i = point; i >= 1; i--) {
		int now = pos[i];
		intree[now] = true;
		ST.modify(a[now].dfn, 0);
		Size.modify(a[now].dfn, 1);
		Light.modify(a[now].dfn, 1);
		renew(now); now = a[now].father;
		while (now != 0) {
			int tmp = Light.pred(a[now].dfn, Light.query(1, a[now].dfn));
			if (tmp >= a[a[now].up].dfn) {
				now = home[tmp];
				renew(now);
				now = a[now].father;
			} else now = a[a[now].up].father;
		}
		ans[i] = curr;
	}
	for (int i = 1; i <= q + 1; i++)
		printf("%lld\n", ans[i]);
	return 0;
}