iis7配置thinkphp网站,10m光纤做网站,如何开外贸公司创业,有关网站建设的网站题号 NC13886 Shortest Path 西南交通大学第十三届ACM决赛 题意#xff1a; 一棵偶数节点的树#xff0c;分成n/2对#xff0c;两两一组#xff0c;所有组的路径之和最小是多少#xff1f; 题解#xff1a; 如果两个点之间相连将另外两个相连的点覆盖#xff0c;那么完全…题号 NC13886 Shortest Path 西南交通大学第十三届ACM决赛 题意 一棵偶数节点的树分成n/2对两两一组所有组的路径之和最小是多少 题解 如果两个点之间相连将另外两个相连的点覆盖那么完全可以改变相连方式 改变后路径更小也就是说两两一组的点都不会覆盖其他点 那么每个点与其他点配对就有两者选择一个与兄弟节点配对中间跨过父亲点另一个就是与父亲节点相连这样选择肯定是最优的 如果这个节点所在的自树里有偶数个节点那么他们内部配对就可以了好像有什么怪怪的 如果有奇数个节点还有把父亲节点拉进来一起配对这样才能组成偶数个 来上代码 #includebits/stdc.h
using namespace std;
const int maxx1e45;
typedef long long ll;
int head[maxx];
int cnt0;
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].uu;edge[cnt].vv;edge[cnt].ww;edge[cnt].nexthead[u];head[u]cnt;}
ll dfs(ll u,ll f,ll w)
{ll sum1;for(int ihead[u];i;iedge[i].next){if(edge[i].v!f)sumdfs(edge[i].v,u,edge[i].w);}if(sum%2)answ;return sum;
}
int main()
{int T;int n;scanf(%d,T);for(int i1;iT;i){cinn;memset(head,0,sizeof(head));cnt0;ans0;for(int i1;in;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
