EdgeWeightAssignment
发布时间
阅读量：
阅读量
编程竞赛题目解析
题解：
通过观察样例推测结论。
关于最小值的探讨：起初未注意到数值必须大于0，因此误以为仅需两个数即可满足条件。然而由于数值必须大于0，因此所使用的数可能为1或3个。当使用1个数时，所有叶子节点的度数奇偶性必须一致；若不一致，则需要使用3个数，并在最后一条边填充与前面异或值相同的数值。
关于最大值的探讨：首先存在一个限制条件，即若两个叶子节点具有相同的祖先，则它们对应的边权值必须相同。此外，在n个节点构成的树中，共有n-1条边，在无额外限制的情况下，可填充的权值种类数量为n-1种。
#include<bits/stdc++.h>
const int N=1e5+10;
using namespace std;
vector<int> g[N];
int dp=-1,flag1=0;
map<int,int> mp;
int ind[N];
void dfs(int u,int dep,int fa)
{
for(int i=0;i<g[u].size();i++){
int j=g[u][i];
if(j==fa) continue;
dfs(j,dep+1,u);
}
if(g[u].全部评论 (0)
还没有任何评论哟~