CF1606F Tree Queries

题意：给定一棵 $n$ 的点的根为 1 的树，定义一次操作为把 $x$ 的所有儿子接到 $x$ 父亲处，并删除 $x$ 。 $q$ 次询问给定 $u, k$ ，输出任意操作之后 $s o n (u) - m k$ 的最大值， $m$ 表示操作次数。 $n, q \leq 2 \times 10^{5}$ ，6s。

比较经典，但是没做过，于是 vp 时没有思路……

首先考虑暴力 DP 的过程，记 $f (u)$ 表示把 $u$ 删除，在删除前的儿子个数（定义比较奇怪？），容易得到转移式：

f (u) = - k + \sum_{v \in s o n (u)} max {1, f (v)}

考虑对其进行化简，记 $s_{u}$ 表示 $u$ 在原树上的儿子，然后可以得到：

f (u) = - k + s_{u} + \sum_{v \in s o n (u)} max {0, f (v) - 1}

注意到如果 $f (v) - k - 1 < 0$ 的话，我们可以认为 $(u, v)$ 不连通，从而达到对 $0$ 取 $max$ 的效果。

现在忽视掉 $max$ 的话，我们可以写出比较好的形式：

\begin{aligned} f (u) = & - k + s_{u} + \sum_{v \in s o n (u)} (f (v) - 1) \\ = & s u m_{u} - (k + 1) s z_{u} + 1 \end{aligned}

$s u m_{u}$ 表示在联通树上在 $u$ 子树内部的原树度数和，所以 $s u m_{u}$ 不是 $s z_{u} - 1$ ，需要注意。

根据这个式子，由于 $f (u)$ 要 $\geq 1$ 才会被认为是向父亲连边了，于是我们可以得到 $k \leq \frac{s u m_{u}}{s z_{u}} - 1$ 时 $f (u)$ 相当于是向父亲连边。

改变联通性过后， $f a (u) \to t o p (u)$ 的 $s u m$ 和 $s z$ 都会发生变化，同理他们的 $k$ 的阈值也会发生变化。但是注意到只有 $t o p (u)$ 的阈值时受关注的，因为其他点都已经向父亲联通了。修改这个可以使用差分转化为单点加子树查，于是树状数组可以做到 $O (n \log n)$ 。

维护所有的阈值只需要用一个 std::priority_queue 维护，计算时将询问按 $k$ 从大到小处理即可。注意 $t o p (u)$ 联通性改变过后，他的阈值一定是变大，所以没必要删除原来的。复杂度 $O (n \log n)$ ，轻松通过。

总结：树上取 $max / min$ 时可以转化为和 0 比较，使用连通性去掉 $max / min$ 。

struct Fenwick {
	int tr[N];
	void add(int x, int c) {
		if (!x) return puts("Failed"), void();
		for (; x < N; x += (x & -x)) tr[x] += c;
	}
	int ask(int x) {
		int res = 0;
		for (; x; x ^= (x & -x)) res += tr[x];
		return res;
	}
} T1, T2;

inline int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }

void dfs(int x, int fa = 0)
{
	nw[dfn[x] = ++ *dfn] = x, ::fa[x] = fa, sz[x] = 1;
	for (int v : g[x])
		if (v ^ fa) dfs(v, x), sz[x] += sz[v];
}

int ask(Fenwick &T, int x) { return T.ask(dfn[x] + sz[x] - 1) - T.ask(dfn[x] - 1); }

void update(int x)
{
	if (vis[x] || x == 1) return;
	vis[x] = true;
	assert(f[x] == x);
	int sz = ask(T1, x), sum = ask(T2, x), anc;
	f[x] = find(fa[x]), anc = find(x);
	// std::cout << "Update " << x << ' ' << sz << ' ' << fa[x] << ' ' << find(fa[x]) << std::endl;
	T2.add(dfn[fa[x]], sum), T1.add(dfn[fa[x]], sz);
	if (fa[anc]) T1.add(dfn[fa[anc]], -sz), T2.add(dfn[fa[anc]], -sum);
	assert(ask(T1, anc) >= 0 && ask(T2, anc) >= 0);
	pq.push({ask(T2, anc) / ask(T1, anc) - 1, anc});
}

signed main()
{
	std::cin >> n;
	for (int i = 1; i <= n; ++ i) f[i] = i;
	for (int i = 1, u, v; i < n; ++ i)
	{
		scanf("%lld %lld", &u, &v);
		g[u].push_back(v), g[v].push_back(u);
	}
	std::cin >> Q;
	for (int i = 1; i <= Q; ++ i) scanf("%lld %lld", &q[i].u, &q[i].k), q[i].id = i;
	std::sort(q + 1, q + Q + 1, [&](Query &q1, Query &q2) {
		return q1.k > q2.k;
	});
	dfs(1);
	for (int i = 1; i <= n; ++ i) {
		T1.add(dfn[i], 1), son[i] = g[i].size() - (i > 1);
		T2.add(dfn[i], son[i]);
		if (i ^ 1)
			T1.add(dfn[fa[i]], -1), T2.add(dfn[fa[i]], -son[i]), pq.push({son[i] - 1, i});
	}
	for (int i = 1, x; i <= Q; ++ i) {
		while (!pq.empty() && pq.top().first >= q[i].k)
			x = pq.top().second, pq.pop(), update(x);
		// std::cout << "Query " << q[i].u << ' ' << q[i].k << ' ' << ask(T1, q[i].u) << ' ' << ask(T2, q[i].u) << '\n';
		res[q[i].id] = ask(T2, q[i].u) - (q[i].k + 1) * ask(T1, q[i].u) + 1 + q[i].k;
		// res[q[i].id] = std::max(res[q[i].id], (int) g[q[i].u].size() - 1);
	}
	for (int i = 1; i <= Q; ++ i) printf("%lld\n", res[i]);
	return 0;
}