并不对劲的CF1338B：Edge Weight Assignment

CF1338B Edge Weight Assignment

题目描述

有一棵(n)个点的无根树，给每条边安排一个任意大小正整数当权值，使任意两个度数为一的点之间的路径的边权异或和为0。
问在所有合法方案中，不同大小的边权最少有几种，最多有几种。
(nleq 10^5)

题解

给这棵树指定一个度数不为1的根。
题面中的限制条件变为：对于任意两个叶子，它们之间的路径的边权异或和为0，也就是它们到根的路径的异或和相等，也就是根到每个叶子的路径异或和相等。
最少种类数：
当所有叶子深度的奇偶性相同时，所有边权都是1就可以；
不同时，发现只有一种或两种边权都不行，有三种边权时，可以把奇（或偶）深度的叶子到父亲的边权安排为2，偶（或奇）深度的叶子到父亲的边权安排为3，其余边安排为1。
最多种类数：
只有当两条边一端连着同一个点，另一端分别连着叶子的时候，这两条边的边权才会必须相同。
我也想知道怎么证啊QAQ

代码

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#define LL long long
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define dwn(i,x,y) for(int i=(x);i>=(y);--i)
#define view(u,k) for(int k=fir[u];~k;k=nxt[k])
#define maxn 100007
#define maxm 200007
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)&&ch!='-')ch=getchar();
	if(ch=='-')f=-1,ch=getchar();
	while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	return x*f;
}
void write(int x)
{
	char ch[20];int f=0;
	if(!x){putchar('0'),putchar('
');return;}
	if(x<0)putchar('-'),x=-x;
	while(x)ch[++f]=x%10+'0',x/=10;
	while(f)putchar(ch[f--]);
	putchar('
');
}
int n,fir[maxn],nxt[maxm],v[maxm],cnte,col[maxn],in[maxn],rt,yes=0,fa[maxn],ans;
void ade(int u1,int v1){v[cnte]=v1,nxt[cnte]=fir[u1],fir[u1]=cnte++;}
void getc(int u)
{
	view(u,k)if(v[k]!=fa[u]){fa[v[k]]=u,col[v[k]]=col[u]^1,getc(v[k]);}
	return;
}
void get2(int u)
{
	int num=0;
	view(u,k)if(v[k]!=fa[u])
	{
		if(in[v[k]]==1)num++;
		get2(v[k]);
	}
	if(num)ans-=num-1;
}
int main()
{
	n=read();memset(fir,-1,sizeof(fir));
	rep(i,2,n){int x=read(),y=read();ade(x,y),ade(y,x),in[x]++,in[y]++;}
	rep(i,1,n)if(in[i]!=1){rt=i;break;}
	getc(rt);int tmp=-1;
	rep(i,1,n)if(in[i]==1)
	{
		if(tmp==-1)tmp=col[i];
		else if(tmp!=col[i]){yes=1;break;}
	}
	if(yes)printf("3 ");
	else printf("1 ");ans=n-1;
	get2(rt);
	write(ans);
	return (~(0-0)+1);
}