自动搬运

查看原文

来自洛谷，原作者为

	5ab_juruo May you find some comfort here

搬运于2025-08-24 22:39:43，当前版本为作者最后更新于2022-07-20 13:05:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

好玩的图论题

普及出构造过分吗？

原题意等价于给边定向。

subtask1,2

暴力，看实现得优秀与否。

subtask3

链。一种原图的弱化情况，不需要考虑旁支，好写一点。 不妨设 $1$ 为左端，$n$ 为右端，且 $s$ 在 $t$ 左侧。

一条链可以被 $s,t$ 分成三部分：$1\sim s$，$s\sim t$，$t\sim n$。

对于第一和第三部分，边的方向是一定的。而对于第二部分，存在一条分界边，左侧的边向 $s$ 指，右侧的边向 $t$ 指。

这个东西可以直接枚举，稍微处理一点前缀和就可以做了。

subtask4

菊花图。考虑到可能有误导的倾向，给的分比较少。

60 分（_ZMF_）

答案为 $\sum_i\min(d(i,s),d(i,t))$，其中 $d(u,v)$ 代表 $u,v$ 在树上的路径长度。

可以 $\mathcal{O}(n\log n)$ 求，也可以倒过来两次 bfs。

证明

假设在最小的方案中，有两条路径相交，则显然两个终点一定不同。设两条路径分别为 $(u,s),(v,t)$。

考虑将其修改成 $(u,t),(v,s)$，注意到两者唯一的区别在于路径不相交，其余路径方向都相同。同时，答案也比原来更优，矛盾。

subtask5

注意到所有边的方向实际上是确定的，直接模拟即可。

subtask6

首先，注意到除了 $(s,t)$ 路径上的边，其余边的方向都是确定的。

其次，在 $(s,t)$ 上一定有一条边 $e$，使得 $e$ 一边都指向 $s$，另一边都指向 $t$，且 $e$ 不定向。

直接枚举 $e$ 即可。

/* name: d
 * author: 5ab
 * created at: 22-06-27 00:06
 */
#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;

typedef long long ll;
const int max_n = 300000;

int hd[max_n], des[max_n<<1], nxt[max_n<<1], val[max_n<<1], f[max_n], fi[max_n], siz[max_n], e_cnt = 0, bne;
ll sdep[max_n], tsm[max_n], tdep[max_n], ssm[max_n];
char ans[max_n];

void add(int s, int t, int v)
{
	des[e_cnt] = t, val[e_cnt] = v;
	nxt[e_cnt] = hd[s], hd[s] = e_cnt++;
}

ll *sm, *dep;
void dfs(int id, int fa)
{
	siz[id] = 1, sm[id] += dep[id], f[id] = fa;
	for (int p = hd[id]; p != -1; p = nxt[p])
		if (des[p] != fa)
		{
			dep[des[p]] = dep[id] + val[p];
			fi[des[p]] = (p >> 1);
			dfs(des[p], id);
			siz[id] += siz[des[p]];
			sm[id] += sm[des[p]];
		}
}

void dfs2(int id, int fa)
{
	for (int p = hd[id]; p != -1; p = nxt[p])
		if (des[p] != fa && (p >> 1) != bne)
		{
			ans[p>>1] = '2' - (p & 1);
			dfs2(des[p], id);
		}
}

inline int read()
{
	int c = getchar(), t = 1, n = 0;
	while (isspace(c)) { c = getchar(); }
	if (c == '-') { t = -1, c = getchar(); }
	while (isdigit(c)) { n = n * 10 + c - '0', c = getchar(); }
	return n * t;
}

void pans(ll x)
{
	if (x >= 10)
		pans(x / 10);
	putchar(x % 10 + '0');
}

signed main()
{
	memset(hd, -1, sizeof hd);
	
	int n = read(), s = read(), t = read();
	
	for (int i = 1, x, y, c; i < n; i++)
	{
		x = read(), y = read(), c = read();
		add(x-1, y-1, c), add(y-1, x-1, c);
	}
	sm = tsm, dep = tdep, dfs(t-1, -1);
	sm = ssm, dep = sdep, dfs(s-1, -1);
	
	ll mxoffset = 0;
	for (int x = t - 1; x != s - 1; x = f[x])
		if (tsm[f[x]] + ssm[x] > mxoffset)
		{
			// cerr << x << " " << dep[x] << " " << siz[x] << " " << fi[x] << endl;
			mxoffset = tsm[f[x]] + ssm[x];
			bne = fi[x];
		}
	
	memset(ans, '0', sizeof(char) * (n - 1));
	dfs2(s-1, -1), dfs2(t-1, -1);
	
	pans(ssm[s-1] + tsm[t-1] - mxoffset);
	printf("\n%s", ans);
	
	return 0;
}