我写了个理论 $O(n)$ 的算法但因为常数巨大，TLE完全在意料之中。

让我不解的是，该算法出现了很多WA。

因此，求证伪该算法或给出小数据Hack。

1. 因为 $s$ 和 $t$ 出度为 $0$，所以总边数为 $n-2$，而原图边数为 $n-1$，所以需要删掉一条边。删掉这条边后显然会形成一个以 $s$ 和 $t$ 为根的森林。

2. 由于删边后要求每个点与 $s$ 或 $t$ 连通，所以删掉的边必定在 $s$ 到 $t$ 的路径上。不妨令 $s$ 为树根。

3. 枚举所有路径上的边，一个一个删。

4. 运用与换根DP类似的思想，我们用 $bel_i$ 表示节点 $i$ 能够到达的最近的在 $s$ 到 $t$ 的路径上的点。显然该点若要到达 $s$ 或 $t$ 需要先经过 $bel_i$。而 $i$ 到 $bel_i$ 的距离是不变的。所以我们只需将 $bel_i$ 的权重增加，然后考虑 $s$ 到 $t$ 这条链。

5. 我们可以 $O(1)$ 从删去一条边的距离和转移到删去另一条边的距离和。

Code:

// dfs1: 跑出s到t的路径
// dfs2: 跑出每个点的bel
// dfs3: 跑出每个边的方向
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, s, t;
struct Edge {
    int from, to, next;
    ll w;
    int type;
    bool disabled;
    Edge() {
        type = 0;
        disabled = false;
    }
} e[600005];
int head[300005], len, del;
int st[300005], top;
ll td, tc, rta;
ll dep[300005];
bool mk[300005];
int bel[300005], wei[300005];
int rev(int a) {
    return ((a - 1) ^ 1) + 1;
}
void Insert(int u, int v, ll w) {
    e[++len].to = v;
    e[len].w = w;
    e[len].next = head[u];
    e[len].from = u;
    head[u] = len;
}
bool dfs1(int u, int prt, int t) {
    bool fl = u == t;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (v != prt) {
            dep[v] = dep[u] + e[i].w;
            st[++top] = i;
            bel[v] = v;
            if (!dfs1(v, u, t)) {
                top--;
                bel[v] = 0;
            }
            else {
                fl = true;
            }
        }
    }
    return fl;
}
void dfs2(int u, int prt) {
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (bel[v] == v) {
            bel[u] = v;
            break;
        }
        if (!bel[v] && v != prt) {
            dfs2(v, u);
            if (bel[v]) {
                bel[u] = bel[v];
            }
        }
    }
    if (bel[u] == u) return;
    for (int i = head[u]; i; i = e[i].next) {
        bel[e[i].to] = bel[u];
    }
}
void dfs3(int u, int prt) {
    for (int i = head[u]; i; i = e[i].next) {
        if (e[i].disabled) continue;
        int v = e[i].to;
        if (v != prt) {
            if (i & 1) {
                e[i].type = 2;
            }
            else {
                e[rev(i)].type = 1;
            }
            dfs3(v, u);
        }
    }
}
int main()
{
    scanf("%d%d%d", &n, &s, &t);
    for (int i = 1; i < n; i++) {
        int u, v;
        ll w;
        scanf("%d%d%lld", &u, &v, &w);
        Insert(u, v, w);
        Insert(v, u, w);
    }
    bel[s] = s;
    dfs1(s, 0, t);
    for (int i = 1; i <= n; i++) {
        if (!bel[i]) dfs2(i, 0);
    }
    for (int i = 1; i <= n; i++) {
        wei[bel[i]]++;
        td += dep[i];
    }
    rta = 1e18;
    for (int i = top; i >= 1; i--) {
        Edge ei = e[st[i]];
        int u = ei.to;
        td -= wei[u] * dep[u];
        if (i != top) {
            td += wei[u] * abs(dep[u] - dep[t]);
        }
        if (td < rta) {
            rta = td;
            del = st[i];
        }
    }
    printf("%lld\n", rta);
    e[del].disabled = e[rev(del)].disabled = true;
    dfs3(s, 0);
    dfs3(t, 0);
    for (int i = 1; i <= len; i += 2) {
        printf("%d", e[i].type);
    }
    return 0;
}