題號 NC13886
Shortest Path
西南交通大學第十三屆ACM決賽
題意：
一棵偶數節點的樹，分成n/2對，兩兩一組，所有組的路徑之和最小是多少？
題解：
如果兩個點之間相連將另外兩個相連的點覆蓋，那么完全可以改變相連方式

改變后路徑更小，也就是說兩兩一組的點都不會覆蓋其他點
那么每個點與其他點配對就有兩者選擇，一個與兄弟節點配對（中間跨過父親點），另一個就是與父親節點相連，這樣選擇肯定是最優的
如果這個節點所在的自樹里有偶數個節點，那么他們內部配對就可以了（好像有什么怪怪的）
如果有奇數個節點，還有把父親節點拉進來一起配對（這樣才能組成偶數個）
來上代碼：

#include<bits/stdc++.h> using namespace std; const int maxx=1e4+5; typedef long long ll; int head[maxx]; int cnt=0; ll x,y,z; ll ans; struct node {ll w,v,u,next; }edge[maxx*2]; void addt(int u,int v,int w) {edge[++cnt].u=u;edge[cnt].v=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt;} ll dfs(ll u,ll f,ll w) {ll sum=1;for(int i=head[u];i;i=edge[i].next){if(edge[i].v!=f)sum+=dfs(edge[i].v,u,edge[i].w);}if(sum%2)ans+=w;return sum; } int main() {int T;int n;scanf("%d",&T);for(int i=1;i<=T;i++){cin>>n;memset(head,0,sizeof(head));cnt=0;ans=0;for(int i=1;i<n;i++){scanf("%lld%lld%lld",&x,&y,&z);addt(x,y,z);addt(y,x,z); }dfs(1,0,0);printf("%d\n",ans);}return 0; } //樹上dfs 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的牛客网【每日一题】Shortest Path 4月3日题目精讲 DFS的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。