专栏文章

题解：P9706 「TFOI R1」Ride the Wind and Waves

llzyqwq
P9706题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min8b9fy
此快照首次捕获于
2025/12/01 22:12
3 个月前
此快照最后确认于
2025/12/01 22:12
3 个月前
查看原文
这个题 800 吧。
O(nk)\mathcal{O}(nk) 做法其他题解写的已经很清楚了，这里讲怎么做到 O(n)\mathcal{O}(n)。
快进到我们需要求出每个点 uu 为根的子树内，到 uu 边数 ≥k\ge k（换根还要用到 k−1k-1 的信息）的点的个数以及路径的边权和。
以边权和为例。朴素的 dp 是转化成求 ≤k\le k 的信息，由于 k≤10k\le 10，记录每个值的答案，从子树合并上来，就是 O(nk)\mathcal{O}(nk)。
这样难以优化。考虑每个点 uu 能对它哪些祖先 vv 的信息产生贡献，显然要求 uu 到 vv 简单路径的边数 ≥k\ge k，那么就是 kk 级祖先根链上的所有点 vv，受到 uu 的贡献为 du−dvd_u-d_v。其中 dud_u 表示 uu 到这棵子树环上的根的路径的边权和。
把贡献写成 pvdv+qvp_vd_v+q_v 的形式，相当于根链 pv,qvp_v,q_v 加。树上差分维护即可。
现在压力给到 kk 级祖先，考虑 dfs 的时候维护根链序列 aa。假设 dfs 到 uu 的时候序列的长度为 mm，那么 kk 级祖先就是 am−ka_{m-k}。这个点 dfs 结束的时候就从末尾删除。可以发现这个过程就是实现一个栈。
这样时间复杂度就是 O(n)\mathcal{O}(n)。
因为写的比较省流所以放个代码。
CPP
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std; typedef long long ll;
const int N = 1000005, K = 12;
int n, k, to[N], rd[N], cir[N << 1], cnt, dep[N], cn;
vector<pair<int, ll>> g[N];
bool vis[N], onc[N];
ll dw[N], ans[N], F[N], tov[N], dis[N << 1], s1[N], s2[N], s3[N], G[N];
ll kf[N], bf[N], bs[N], kg[N], bg[N], bt[N];
int arr[N];
void dfs1(int u) {
	arr[++cn] = u;
	if (cn >= k) {
		--kf[arr[cn - k]]; bf[arr[cn - k]] += dw[u];
		--kg[arr[cn - k + 1]]; bg[arr[cn - k + 1]] += dw[u];
		++bt[arr[cn - k]]; ++bs[arr[cn - k + 1]];
	}
	for (auto [v, w] : g[u]) {
		if (!onc[v]) {
			dep[v] = dep[u] + 1; dw[v] = dw[u] + w; dfs1(v);
		}
	}
	--cn;
}
void dfs3(int u) {
	for (auto [v, w] : g[u])
		if (!onc[v]) {
			dfs3(v);
			kf[u] += kf[v]; bf[u] += bf[v];
			kg[u] += kg[v]; bg[u] += bg[v];
			bs[u] += bs[v]; bt[u] += bt[v];
		}
	F[u] = kf[u] * dw[u] + bf[u];
	G[u] = kg[u] * dw[u] + bg[u];
	//cout << u << ' ' << bs[u] << ' ' << bt[u] << '\n';
}
void dp(int u, ll cur, ll sum, ll val) {
	ans[u] = cur + val * sum;
	for (auto [v, w] : g[u]) {
		if (!onc[v]) {
			ll cur_ = ans[u];
			ll sum_ = sum + F[u] - G[v] - w * bs[v];
			dp(v, cur_, sum_, w);
		}
	}
}
void dfs2(int u, ll x, ll y) {
	ans[u] += x + dw[u] * y;
	for (auto [v, w] : g[u]) if (!onc[v]) dfs2(v, x, y);
}
int main() {
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin >> n >> k;
	for (int i = 1, u, v, w; i <= n; ++i)
		cin >> u >> v >> w, ++rd[v], g[v].eb(u, w), to[u] = v, tov[u] = w;
	bool flg = 0;
	for (int i = 1; i <= n; ++i) {
		if (!rd[i]) {
			vector<int> tmp;
			int u = i;
			while (1) {
				tmp.eb(u);
				if (vis[to[u]]) {
					bool fg = 0;
					for (int j : tmp) {
						if (j == to[u]) fg = 1;
						if (fg) cir[++cnt] = j, onc[j] = 1, dis[cnt] = tov[j];
					}
					break;
				} else u = to[u], vis[u] = 1;
			}
			flg = 1; break;
		}
	}
	// for (int i = 1; i <= cnt; ++i) cout << cir[i] << '\n';
	if (!flg) {
		for (int i = 1; i <= n; ++i) cout << "0\n"; return 0;
	}
	// for (int i = 1; i <= cnt; ++i) cout << cir[i] << '\n';
	for (int i = 1; i <= cnt; ++i) {
		dfs1(cir[i]); dfs3(cir[i]); dp(cir[i], 0, 0, 0);
	}
	//for (int i = 1; i <= n; ++i) cout << bs[i] << ' ' << bt[i] << '\n';
	for (int i = 1; i <= cnt; ++i) cir[i + cnt] = cir[i], dis[i + cnt] = dis[i];
	for (int i = cnt * 2; i >= 1; --i)
		dis[i] += dis[i + 1],
		s1[i] = s1[i + 1] + F[cir[i]],
		s2[i] = s2[i + 1] + dis[i] * F[cir[i]];
	for (int i = 1; i <= cnt; ++i)
		dfs2(cir[i], dis[i] * (s1[i + 1] - s1[i + cnt]) - (s2[i + 1] - s2[i + cnt]), s1[i + 1] - s1[i + cnt]);
	for (int i = 1; i <= n; ++i) cout << ans[i] << '\n';
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...