调了几个小时了,调不出来错,求助dalao
查看原帖
调了几个小时了,调不出来错,求助dalao
120017
JeffZhao楼主2021/7/2 19:53
#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10;

int n;
int p[N], dfn[N], tag[N << 2], sum[N << 2];
int siz[N], O;

int head[N << 1], nx[N << 1], ver[N << 1], cnt;
inline void add(int x, int y) {
	ver[++cnt] = y;
	nx[cnt] = head[x]; head[x] = cnt;
	return;
}

inline void dfs(int u, int fa) {
	siz[u] = 1;
	dfn[u] = ++O;
	for (int i = head[u]; i; i = nx[i]) {
		int v = ver[i];
		if (v == fa)continue;
		dfs(v, u);
		siz[u] += siz[v];
	}
	return;
}
inline void Add(int k, int l, int r, int v) {
	sum[k] = (r - l + 1) * v;
	tag[k] += v;
	return;
}
inline void pushdown(int k, int l, int r) {
	if (tag[k] == 0)
		return;
	int mid = (l + r) >> 1;
	Add(k << 1, l, mid, tag[k]);
	Add(k << 1 | 1, mid + 1, r, tag[k]);
	tag[k] = 0;
	return;
}
inline void update(int k, int l, int r, int ql, int qr, int v) {
	if (ql <= l && r <= qr) {
		Add(k, l, r, v);
		return;
	}
	pushdown(k, l, r);
	int mid = (l + r) >> 1;
	if (ql <= mid)update(k << 1, l, mid, ql, qr, v);
	if (qr > mid)update(k << 1 | 1, mid + 1, r, ql, qr, v);
	sum[k] = sum[k << 1] + sum[k << 1 | 1];
	return;
}
inline int query(int k, int l, int r, int where) {
	if (l > where || r < where)
		return 0;
	if (l == r && l == where)
		return sum[k];
	pushdown(k, l, r);
	int mid = (l + r) >> 1, res = 0;
	res += query(k << 1, l, mid, where);
	res += query(k << 1 | 1, mid + 1, r, where);
	return res;
}

int main(void) {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> n;

	for (int i = 1; i < n; ++i) {
		int x, y;
		cin >> x >> y;
		add(x, y);
		add(y, x);
	}

	for (int i = 1; i <= n; ++i)
		cin >> p[i];

	dfs(1, -1);

	//for (int i = 1; i <= n; ++i)
		//cout << dfn[p[i]] << " ";

	for (int i = 1; i <= n; ++i) {
		cout << query(1, 1, n, dfn[p[i]]) << endl;
		update(1, 1, n, dfn[p[i]], dfn[p[i]] + siz[p[i]] - 1, 1);
	}

	return 0;
}

2021/7/2 19:53
加载中...