[ABC361E] Tree and Hamilton Path 2 题解

zrl123456 · 2024-07-09 10:29:53 · 题解

[ABC361E] Tree and Hamilton Path 2
考察：树的直径，dfs，dp。
题目简述：
给定一棵有 n 个点的树，从任意一个点开始，经过所有点后所走过的最短路径。
一个点可以经过多次，最后不一定要回到原点。
数据范围：

• n\le 2\times 10^5

  考虑下图：
  
  其满足限制的最短路径是 9\Rightarrow6\Rightarrow1\Rightarrow2\Rightarrow7\Rightarrow2\Rightarrow4\Rightarrow5\Rightarrow8\Rightarrow5\Rightarrow3，长度为 4+3+2+5+5+3+5+1+1+4=33。
  我们将其标在树上，就成了下图： 我们发现有向图比原树少了 3 到 9 的这一条路径，而这条路径就是树的直径。
  那么我们得出答案就是（设直径为 len）：

  \sum_{(u_i,v_i,w_i)\in E}w_i-len

  直径采用 dp 就可得到。

代码：

#include<bits/stdc++.h>
#define inl inline
#define reg register
#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=(y);++i) 
#define per(i,x,y) for(reg int i=x;i>=(y);--i)
#define rpr(i,x,y,z) for(reg int i=x;i<=(y);i+=z)
#define epe(i,x,y,z) for(reg int i=x;i>=(y);i-=z)
#define endl '\n'
#define INF 1e16
#define pb push_back
#define fi first
#define se second
#define lcm(x,y) x/__gcd(x,y)*y
#define ull unsigned long long
#define prr make_pair
#define pii pair<int,int> 
#define gt(s) getline(cin,s)
#define at(x,y) for(reg auto x:y)
#define ff fflush(stdout)
#define mt(x,y) memset(x,y,sizeof(x))
#define idg isdigit
#define fp(s) string ssss=s;freopen((ssss+".in").c_str(),"r",stdin);freopen((ssss+".out").c_str(),"w",stdout);
#define sstr stringstream 
#define all(x) x.begin(),x.end()
#define mcy(a,b) memcpy(a,b,sizeof(b))
using namespace std;
const int N=2e5+5;
vector<pii >g[N];
int mx[N],mx2[N];
bool vis[N];
inl void dfs(int u,int &num){
    vis[u]=1;
    at(v,g[u])
        if(!vis[v.fi]){
            dfs(v.fi,num);
            if(mx[u]<mx[v.fi]+v.se){
                mx2[u]=mx[u];
                mx[u]=mx[v.fi]+v.se;
            }else mx2[u]=max(mx2[u],mx[v.fi]+v.se);
        }
    num=max(num,mx[u]+mx2[u]);
}
signed main(){
    fst;
    reg int n,num=0,ans=0;
    cin>>n;
    rep(i,2,n){
        reg int u,v,w;
        cin>>u>>v>>w;
        g[u].pb(prr(v,w));
        g[v].pb(prr(u,w));
        ans+=w<<1;
    }
    dfs(1,num);
    cout<<ans-num;
    return 0;
}