题面
Today HH becomes a designer, and he faces a problem so he asks you for help.
Treeisland is a country with n cities and n−1 two-way road and from any city you can go to any other cities.
HH the designer is going to design a plan to divide n city into n/2 pairs so that the sum of the length between the n/2 pairs city is minimum.
Now HH has finished it but he doesn't know whether it's true so he ask you to calculate it together.
It's guaranteed that n is even.
题解
今天的题很简单啊~
首先我们仔细观察一下样例2,可以发现我们好像不论怎么选择 所得到的解都是所有边的权值和。那什么情况下能减少这个最终答案呢?观察样例1,很容易看出来当一条边的两边的点数都为偶数时,那这条边就不需要被选择了。
所以我们先统计一下所有边的和,然后dfs枚举看哪条边满足上述条件,那么对应的答案减掉这条边的权值就可以啦!!
#include<bits/stdc++.h> #define pb push_back #define fi first #define se second #define ios ios::sync_with_stdio(0); using namespace std; typedef long long LL; typedef pair<int, int> PII; typedef vector<int> VI; const int maxn = 2e6 + 6; const LL inf = 0x3f3f3f3f; const int mod = 998244353; LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;} //head struct Ed{ int to,w,next; }edge[maxn]; int tot,head[maxn],sz[maxn]; void add(int u,int v,int w){ edge[++tot]={v,w,head[u]}; head[u]=tot; } int t,n; LL ans; void dfs(int u,int fa){ sz[u]=1; for(int i=head[u];i;i=edge[i].next){ int v=edge[i].to,w=edge[i].w; if(v==fa) continue; dfs(v,u); sz[u]+=sz[v]; if((n-sz[v])%2==0&&(sz[v]%2==0)) ans-=w; } } int main(){ scanf("%d",&t); while(t--){ scanf("%d",&n); ans=0;tot=0; for(int i=1;i<=n;i++) head[i]=0; for(int i=1,u,v,w;i<n;i++){ scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); ans+=w; } dfs(1,-1); printf("%lld\n",ans); } }