题意:给出一棵有边权的树,两个人从st出发,需要经过树上所有的点,问最少代价。
数据范围:点数$n<=1e5$

trick:

思考这样的问题想要途径所有的点那么必然不可避免的需要走回头路,如何选一条路使得在这个路上我们只需要走一遍,其他路走两遍?那么也就是在较短的子树上来回走,显然沿着的路就是树的最长路即树的直径。
树的直径采用$O(n)$的两边dfs,每次可以确定直径的一个端点,两遍即可定直径。

Code:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
typedef long long ll;
struct node {
    int to,next,w;
}e[maxn];
int cnt;
int head[maxn];
void addedge2(int u,int v,int w) {
    e[cnt]=node{u,head[v],w}; head[v]=cnt++;
    e[cnt]=node{v,head[u],w}; head[u]=cnt++;
}
int dis[maxn];
void init() {
    memset(dis,0, sizeof(dis));
    memset(head,-1,sizeof(head));
    cnt = 0;
}
void dfs(int u,int fa,int d) {
    for(int i=head[u];~i;i=e[i].next) {
        int v = e[i].to, w = e[i].w;
        if(v!=fa) {
            dis[v] = w + d;
            dfs(v,u,w+d);
        }
    }
}
int main() {
    int st,n;scanf("%d%d",&amp;n,&amp;st);
    init();int TOT = 0;
    for(int i=1;i<=n-1;i++){
        int u,v,w;scanf("%d%d%d",&amp;u,&amp;v,&amp;w);
        addedge2(u,v,w);TOT += 2*w;
    }
    dfs(st,-1,0);
    int id=0,MAX = -1;
    for(int i=1;i<=n;i++)
        if(dis[i] > MAX) MAX = dis[i], id = i;
    dis[id]=0;
    dfs(id,-1,0);MAX = -1;
    for(int i=1;i<=n;i++) MAX = max(MAX,dis[i]);
    return !printf("%d\n",TOT-MAX);
}
分类: 图论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.