题解：CF1527D MEX Tree

某模拟赛 T1，赛后发现爆标（题解是

\operatorname{LCA}

做法），遂来写题解。

我们发现不含

0

的路径

\operatorname{mex} = 0

。含

0

的路径

\operatorname{mex} > 0

，所以可以先单独计算不含

0

的路径数，求出

ans_0

。
对于含

0

的路径，我们可以从

1

开始枚举新添的数，并把它尝试添进答案路径中，维护答案。我们发现，添加进入答案序列并不需要

\operatorname{LCA}

，只需要暴力跳父亲，因为每个点最多访问一次，所以复杂度为均摊

\operatorname{O}(n)

。~~爆标了！！~~

code

CPP

#include<bits/stdc++.h>
using namespace std;
#define N 200005
int n, f[N], siz[N];
long long ans[N];
bool book[N];
vector<int> mp[N];
inline dfs(int x, int y) {
	f[x] = y, siz[x] = 1;
	for(int i = mp[x].size() - 1; ~i; --i) {
		int to = mp[x][i];
		if(to ^ y) {
			dfs(to, x);
			if(!x) ans[0] += 1ll * (siz[to] - 1) * siz[to] >> 1;
			siz[x] += siz[to];
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--) {
		cin >> n;
		if(n == 1) {
			puts("0 0");
			continue;
		}
		for(int i = n - 1; i; --i) {
			int u, v;
			cin >> u >> v;
			mp[u].push_back(v), mp[v].push_back(u);
		}
		dfs(0, 0);
		int l = 1, r = 0, now = 1, as = 1;
		while(f[now]) book[now] = 1, now = f[now];
		book[now] = 1, book[0] = 1;
		while(book[as]) ++as;
		siz[0] -= siz[now];
		ans[1] = 1ll * siz[0] * (siz[now] - siz[1]);
		int sz = siz[0];
		for(int i = mp[0].size() - 1; ~i; --i) {
			int to = mp[0][i];
			if(to ^ now) sz -= siz[to], ans[1] += 1ll * sz * siz[to];
		}
		for(int i = as; i < n; i = as) {
			int ii = i;
			while(!book[f[ii]]) book[ii] = 1, ii = f[ii];
			book[ii] = 1;
			if(f[ii] == l) {
				while(book[as]) ++as;
				ans[i] = 1ll * siz[r] * (siz[l] - siz[i]);
				l = i;
			} else if(f[ii] == r) {
				while(book[as]) ++as;
				ans[i] = 1ll * siz[l] * (siz[r] - siz[i]);
				r = i;
			} else break;
		}
		ans[as] = 1ll * siz[l] * siz[r];
		for(int i = 0; i <= n; ++i) {
			printf("%lld ", ans[i]);
			ans[i] = book[i] = siz[i] = f[i] = 0;
			mp[i].clear();
		}
		putchar('\n');
	}
	return 0;
}

题解：CF1527D MEX Tree

文章操作

code

相关推荐

评论

题解：CF1527D MEX Tree