【每日一题】Shortest Path

Shortest Path

思路：

由题意可知是一个树形结构。若要使两两之间边权最小，尽量不能选重边，也就是说尽可能在节点所在子树里寻找答案。显然与叶子节点相连的边必须选。
假设当前结点为x，如果tot[x]&1==1也就是x的子树的结点数(包括x自己)为奇数时，x和父亲的边就一定要选，即答案加上edge[x].w----表示为x与父亲组成的边，当然如果它的兄弟和父亲也连了就刚好两个兄弟组成一个点对，它们的边长为他们分别与父亲的边的和。
如果tot[x]&1==0也就是x的子树的结点数(包括x自己)为偶数时，那么肯定在子树里面就互相连完了，它不需要向上连父结点。

代码

#include <bits/stdc++.h>
#define ll long long
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
struct tree{
    int t,w,next;
}edge[20005];
int t,n,cnt;
int head[10005],tot[10005];
ll ans;
void add(int u,int v,int len) {
    edge[++cnt].t=v;
    edge[cnt].w=len;
    edge[cnt].next=head[u];
    head[u]=cnt;
}//构造一棵无向树
void dfs(int u,int fa,int len) {
    tot[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next) { //遍历儿子结点,因为是无向的,
        int v=edge[i].t;                      //所以父结点和儿子结点会因为遍历的起点不同而不同.
        if(v==fa)    continue;    //已经遍历到叶子结点了
        dfs(v,u,edge[i].w);    //edge[i].w为它与父亲组成的边
        tot[u]+=tot[v];        //tot[x]表示包括结点x共有几个点 
    }
    if(tot[u]&1)    ans+=len; 
}
int main() {
    js;
    cin>>t;
    while(t--) {
        ans=cnt=0;
        cin>>n;
        memset(head,-1,sizeof head);
        for(int i=2;i<=n;++i) {
            int u,v,w;
            cin>>u>>v>>w;
            add(u,v,w);
            add(v,u,w);
        }
        dfs(1,0,0);
        cout<<ans<<endl;
    }
}