AGC029E Wandering TKHS

没有简要题意了，哈哈！

分析一下题目给出的过程。直觉告诉我们关键在于点 \(r\) 到 \(1\) 的这条路径。一个结论是整个过程中访问的编号最大的点就是这条路径上的最大点，证明可以考虑如果访问了不在路径上的更大的点，在此之前一定可以够到 \(1\)，于是矛盾。

于是可以发现最大值很重要，那么直觉告诉我们首先观察一下全局最大值，假设这个点是 \(s\)。这个点很厉害，所有在它子树外的点都永远不会进入它这个子树。所以当我们计算它子树外的节点的答案时，我们可以直接把 \(s\) 的一整个子树全部删除，然后接着找剩下的全局最大值，递归进行。而所有 \(s\) 子树内的节点，在访问完 \(s\) 以后，它在子树外的行为都和 \(s\) 的父亲完全相同。那么在最后对答案做一个类似前缀和的操作即可。现在我们只要考虑子树内部的答案和 \(s\) 自己的答案。

假设 \(s\) 有 \(k\) 个儿子，那么总共有 \(k\) 个小子树，考虑任何一棵小子树里面的某个点，在这个点访问 \(s\) 之前，它一定要把子树内还没有被删除的所有点全部访问一遍（因为 \(s\) 是当前全局最大值）。于是这部分的贡献可以直接算出来。然后它到达了 \(s\)，如果它往子树外面走，刚才已经说明，这部分贡献是可以直接从 \(s\) 的父亲的答案获得的，于是只需要考虑它折下去进入另一个小子树。你会发现，它能走到那些点，取决于它到达 \(s\) 以后，往根走的那段路上的最大值，这是因为我们一开始给出的结论。那么这个贡献对于所有小子树都很好算，直接预处理出来即可。

时间复杂度线性，只需要用 DFS。

// Author: kyEEcccccc

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
using ULL = unsigned long long;

#define F(i, l, r) for (int i = (l); i <= (r); ++i)
#define FF(i, r, l) for (int i = (r); i >= (l); --i)
#define MAX(a, b) ((a) = max(a, b))
#define MIN(a, b) ((a) = min(a, b))
#define SZ(a) ((int)((a).size()) - 1)

constexpr int N = 200005;

int n;
vector<int> to[N];

int par[N];
int mx[N];

void init_tree(int u)
{
	MAX(mx[u], u);
	for (auto v : to[u])
	{
		if (v == par[u]) continue;
		par[v] = u;
		mx[v] = mx[u];
		init_tree(v);
	}
}

int bel[N];

int dfs1(int u)
{
	int res = 1;
	for (auto v : to[u])
	{
		if (v == par[u] || bel[v] != 0) continue;
		res += dfs1(v);
	}
	return res;
}

int dfs2(int u, int lim)
{
	if (u > lim) return 0;
	int res = 1;
	for (auto v : to[u])
	{
		if (v == par[u] || bel[v] != 0) continue;
		res += dfs2(v, lim);
	}
	return res;
}

int ans[N];

void dfs3(int u, int x, int b)
{
	ans[u] = x;
	bel[u] = b;
	for (auto v : to[u])
	{
		if (v == par[u] || bel[v] != 0) continue;
		dfs3(v, x, b);
	}
}

void dfs4(int u)
{
	for (auto v : to[u])
	{
		if (v == par[u]) continue;
		ans[v] += ans[bel[v]];
		dfs4(v);
	}
}

signed main(void)
{
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(nullptr);

	cin >> n;
	F(i, 1, n - 1)
	{
		int u, v; cin >> u >> v;
		to[u].push_back(v);
		to[v].push_back(u);
	}

	init_tree(1);

	FF(u, n, 2)
	{
		if (bel[u] != 0) continue;
		vector<pair<int, pair<int, int>>> sub;
		int sum2 = 0;
		for (auto v : to[u])
		{
			if (v == par[u] || bel[v] != 0) continue;
			sub.push_back({v, {dfs1(v), dfs2(v, mx[par[u]])}});
			sum2 += sub.back().second.second;
		}
		ans[u] = sum2 + 1;
		bel[u] = par[u];
		for (auto t : sub) dfs3(t.first, sum2 + 1 - t.second.second + t.second.first, par[u]);
	}

	dfs4(1);

	F(i, 2, n) cout << ans[i] << " \n"[i == n];
	
	return 0;
}