CF1338B Edge Weight Assignment

前情提要两包纸有一包被偷了不嘻嘻。题意给你一个n个顶点的无权树让你为每条边都赋一条正权值使得树中任意两个叶子节点的简单路径上所有边的权值的按位异或结果必须等于 0。定义f为所有权值中的不同的值输出最小的f与最大的f。做法最小值如果所有叶子对路径长度均为偶数直接放一种数就好了。如果是奇数就要类似于b^ca剩下的都填a答案只有1或者3两种答案。当所有叶子到根的距离都同奇偶时答案就是 1 。否则是 3 。最大值答案就是总边数减叶子个数加叶子父亲数量。先假设随便放答案是n-1。考虑不合法的每个叶子的叶子兄弟和他们父亲的边权都应该一样。于是应该减去叶子个数再加上每个叶子父亲组内部的一种边。这样所有加在一起就是叶子个数加叶子父亲数量。代码(求赞)#includebits/stdc.h using namespace std; const int N1e55; int n,rt,cnt[N],dep[N],fa[N],d[N]; bool flag[N]; vectorint mp[N],res; void dfs(int u,int pa){ dep[u]dep[pa]1; fa[u]pa; for(int i0;imp[u].size();i){ int vmp[u][i]; if(vpa) continue; dfs(v,u); } } int main(){ scanf(%d,n); for(int i1;in;i){ int u,v; scanf(%d%d,u,v); cnt[u],cnt[v]; if(cnt[u]2) rtu; if(cnt[v]2) rtv; mp[u].push_back(v); mp[v].push_back(u); } dfs(rt,0); int ansn-1; for(int i1;in;i) d[fa[i]]; for(int i1;in;i){ if(d[i]0){ res.push_back(dep[i]); ans--; if(flag[fa[i]]false){ flag[fa[i]]true; ans; } } } bool fl(res[0]-1)1,tagtrue; if(res.size()1) tag(res[0])1; for(int i1;ires.size();i){ bool fffl; fl(res[i]-1)1; if(fl!ff) tagfalse; } printf(%d %d,(tag ? 1 : 3),ans); return 0; }