普及模拟赛 R1 D 题解

· · 题解

好玩的图论题

普及出构造过分吗？

原题意等价于给边定向。

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;
}