[ABC361E] Tree and Hamilton Path 2 题解

FFTotoro · 2024-07-07 09:36:19 · 题解

第一次 3 分钟内做掉 E。

先假定根结点为 1，即从结点 1 开始遍历整棵树。如果最后要回到根结点，考虑深搜的过程，显然每条边要经过恰好 2 次（根向叶子下行 / 叶子向根上行）；因为最后不需要回到根结点，所以可以留下一条根结点到叶子的路径不返回，即答案可以减去 1 到某个结点的路径长度，为了让答案最小，只需要找出最长的那条路径即可。

如果根结点不为 1，显然考虑选择一个根结点和一个叶子结点作为那条路径。显然此时只需选取树的直径即可。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,c=0; cin>>n;
  vector<vector<pii> > g(n);
  for(int i=1;i<n;i++){
    int u,v,w; cin>>u>>v>>w,c+=w<<1;
    g[--u].emplace_back(--v,w);
    g[v].emplace_back(u,w);
  }
  vector<int> d(n);
  function<void(int,int)> dfs=[&](int u,int f){
    for(auto [i,w]:g[u])
      if(i!=f)d[i]=d[u]+w,dfs(i,u);
  }; // 两遍 dfs 求直径
  dfs(0,0);
  int rt=max_element(d.begin(),d.end())-d.begin();
  fill(d.begin(),d.end(),0);
  dfs(rt,rt);
  cout<<c-*max_element(d.begin(),d.end())<<endl;
  return 0;
}