第一问很好求，相当于是所有点到 $s$ 或 $t$ 中较近的点的最短路径之和。换句话说，把 $s$ 与 $t$ 分别作为起点，跑两遍最短路后得到 $diss,dist$ 分别表示最短路，则答案即为 $\sum\limits_{i = 1}^{n} \min (diss_i,dist_i)$。又由于题目给的是一棵树，所以其实距离就相当于普通的子树向父亲节点的转移。第一问的代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
| void dfs (int u,int fa,ll *dis)
{
for (int i = head[u];i;i = nxt[i])
{
int v = to[i];
if (v == fa) continue;
dis[v] = dis[u] + val[i];
dfs (v,u,dis);
}
}
dfs (s,0,dis1);dfs (t,0,dis2);
for (int i = 1;i <= n;++i) ansdis[i] = min (dis1[i],dis2[i]),ans += ansdis[i];
printf ("%lld\n",ans);
|
第二问相当于是还原路径，再次跑两遍最短路，当跑到一个节点 $u$ 时，若发现 $ansdis_u$ 加上边权后恰好等于 $ansdis_v$，也就是说这是一个可能的还原方式，把这个点所在的边标记一下。
当所有点标记以后，尝试进行判断出入边。考虑第 $i$ 条双向边满足边的下标 $x,y$ 为 $2i,2i+1$ 时存在性质 $x \oplus 1 = y,y \oplus 1 = x$，所以当下标为奇数时相当于从起点 $s,t$ 的出边，在构造答案时需要注意出入恰好反向。于是我们便得到了第二问的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void solve (int u,int fa)
{
for (int i = head[u];i;i = nxt[i])
{
int v = to[i];
if (v == fa) continue;
if (min (dis1[v],dis2[v]) == ansdis[u] + val[i]) vis[v] = i;
solve (v,u);
}
}
solve (s,0);solve (t,0);
for (int i = 1;i <= n;++i)
{
if (!vis[i]) continue;
ty[vis[i] >> 1] = (vis[i] & 1) ? 1 : 2;
}
for (int i = 1;i < n;++i) printf ("%d",ty[i]);
|
