牛客网【每日一题】Shortest Path 4月3日题目精讲 DFS

题号 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