题面

题目名称巡访

问题描述

　　$Chanxer$ 终于当上了“中华农民联盟”的盟主，他举目四望，决定四处走走，巡视自己的农土。

　　“中华农民联盟”的成员有个村庄，在“村村通”计划中，村庄们被条道路联通了起来， $Chanxer$ 计划从某个村庄出发，访问所有的村庄。

可是 $Chanxer$ 出行有一个特殊的要求，那就是必须以农车代步，现在我们知道哪些村庄配备有农车，也就是说，只有配备有农车的村庄才能够被作为出发点。

$Chanxer$ 有点懒，他想知道访问全部的村庄所要走的路程长度最小是多少。

输入格式

输入文件共 $n+1$ 行：

第一行一个正整数 $n.$

第 $2\sim n$ 行每行三个正整数 $x_i,y_i,z_i$ 表示 $x_i$ 号村庄和 $y_i$ 号村庄之间有一条长度为 $z_i$ 的路。

接下来一行包含 $n$ 个 $0/1$，表示第 $i$ 个数是否能作为起始点。

输出格式

输出一行表示最小路径长度，数据保证存在。

样例

输入

输出

样例解释

样例所示图如下图：（其中 $1,2,3$ 可作为起点）

选择 $2$ 号点时最优，最优路径为 $2\to 1\to 3\to 4\to 3\to 5$

数据范围

对于 $60\%$ 测试点有 $n\leq10$

对于 $100\%$ 测试点有 $n\leq10^6,1\leq x_i,y_i\leq n, 1\leq z_i\leq 10^4$

题解

Sol

线性的换根 $dp$

首先，题目要求的路径并不是很方便直接求出来，那么我们想一想怎么把最短路径转化一下。为了走过的路径最短，我们肯定尽量不能走回头路，那么就是说要让重复走的距离最短。换句话说，也就是让不走的距离最长。那么我们显然还可以先走掉其他重复走的路，再一头扎进从当前点出发最长的那条链中。那么题意可以转化成求从一些点出发的最长链的长度了。

那么，我们先随便指定一个点是根，我们考虑吧每一个 $u$，那么答案可能是 $u$ 所在子树里面的一条链，也可能是 $u$ 向父亲伸出去的一条链。这就是换根 $dp$ 的思想了，可以通过两遍 $dfs$ 分别求出答案。

我们设第一种答案是 $f_i$ ，第二种是 $g_i$，$f_i$ 可以常规树形 $dp$ 求，而 $g_i$ 则要单独考虑：它可以从父亲的其他儿子或者父亲的 $g_i$ 转移过来，因此我们需要知道 $f_i$ 对应的是哪一个儿子 $to_i$，以及次大长的链 $h_i.$ 然后转移方程就显然了。

$code:$

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <vector>
#define INF 0x3f3f3f3f
#define NO 100005
#define MO 1000005
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second
#define fup(i, x, y) for(register int i = x; i <= y; ++i)
#define lln putchar('\n')
#define blk putchar(' ')
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
ll read()
{
    ll ret = 0;
    char ch = ' ', last;
    while (ch < '0' || ch > '9')
        last = ch, ch = getchar();
    while (ch >= '0' && ch <= '9')
        ret = ((ret + (ret << 2)) << 1) + (ch ^ '0'), ch = getchar();
    return last == '-' ? -ret : ret;
}
void write(ll x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
//head

int n, cnt, head[NO], f[NO], g[NO], s, f2[NO], to[NO], ans;
struct node
{
    int ne, v, c;
}e[MO];
//variable

void add(int u, int v, int c)
{
    e[++cnt].ne = head[u];
    e[cnt].v = v;
    e[cnt].c = c;
    head[u] = cnt;
}
void dfs1(int u, int la)
{
    for (int i = head[u]; i; i = e[i].ne)
        if (e[i].v != la)
        {
            dfs1(e[i].v, u);
            if (f[e[i].v] + e[i].c > f[u])
                f2[u] = f[u], f[u] = f[e[i].v] + e[i].c, to[u] = e[i].v;
            else
                f2[u] = max(f2[u], f[e[i].v] + e[i].c);
        }
}
void dfs2(int u, int la, int li)
{
    g[u] = max(g[la], (to[la] == u ? f2[la] : f[la])) + e[li].c;
    for (int i = head[u]; i; i = e[i].ne)
        if (e[i].v != la)
            dfs2(e[i].v, u, i);
}
void init()
{
    freopen("path.in", "r", stdin);
    freopen("path.out", "w", stdout);
    n = read();
    fup (i, 1, n - 1)
    {
        int x = read(), y = read(), z = read();
        add(x, y, z), add(y, x, z), s += z;
    }
    dfs1(1, 0), dfs2(1, 0, 0);
    fup (i, 1, n)
    {
        int x = read();
        if (x)
            ans = max(ans, max(f[i], g[i]));
    }
    write(s * 2 - ans), lln;
}
//function

int main()
{
    init();
    return 0;
}
//main

Data

download

题面

题目名称 巡访