自动搬运

查看原文

来自洛谷，原作者为

	GI录像机 除了OI，除了这个世界，我还是剩点东西的

搬运于2025-08-24 22:48:36，当前版本为作者最后更新于2023-10-30 11:44:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

容易发现当一些奖牌同时被一个人获取以后，这些奖牌之后的命运将会完全一致。

这就很像是树上的节点往上走，lca 后的祖先都是一样的。

我们可以利用树的结构来完成操作。

每当一个选手 $x$ 打败选手 $y$ 时，会出现一个全新的奖牌 $i$。我们可以将选手 $x$ 和 $y$ 原有的奖牌连接到 $i$ 上。这样等到 $x$ 被打败时，$i$ 子树内的奖牌被 $x$ 持有的时间就会增加。这样，每个选手在任意时刻持有的奖牌都是一棵完整的树，操作时我们只需要对树根连边即可。

结束时，直接遍历每一棵树，计算奖牌在谁手中持有的时间最长。

代码：

#include<bits/stdc++.h>
using namespace std;
int read() {
	int f = 1, x = 0;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-')f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = x * 10 + c - '0';
		c = getchar();
	}
	return f * x;
}
void write(int x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x > 9)write(x / 10);
	putchar(x % 10 + '0');
}
const int N = 2e5 + 10, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
struct Edge {
	int to, nxt;
} e[N];
int n = read(), m = read(), las[N], head[N], tot, id[N], num[N], sum[N], ans[N];
void add(int u, int v) {
	e[++tot].to = v;
	e[tot].nxt = head[u];
	head[u] = tot;
}
void dfs(int pos, int maxn, int maxnid) {
	sum[id[pos]] += num[pos];
	if (sum[id[pos]] > maxn) {
		maxn = sum[id[pos]];
		maxnid = id[pos];
	} else if (sum[id[pos]] == maxn)maxnid = min(maxnid, id[pos]);
	ans[maxnid]++;
	for (int i = head[pos]; i; i = e[i].nxt)dfs(e[i].to, maxn, maxnid);
	sum[id[pos]] -= num[pos];
}
signed main() {
	memset(las, -1, sizeof(las));
	for (int i = 0; i < m; i++) {
		int x = read(), y = read();
		if (las[x] != -1) {
			id[las[x]] = x;
			num[las[x]] = i - las[x];
			add(i, las[x]);
		}
		if (las[y] != -1) {
			id[las[y]] = y;
			num[las[y]] = i - las[y];
			add(i, las[y]);
		}
		las[y] = -1;
		las[x] = i;
	}
	for (int i = 0; i < n; i++)
		if (las[i] != -1) {
			id[las[i]] = i;
			num[las[i]] = m - las[i];
			dfs(las[i], 0, 0);
		}
	for (int i = 0; i < n; i++) {
		write(ans[i]);
		putchar(' ');
	}
	return 0;
}