本文共 2554 字，大约阅读时间需要 8 分钟。

$--------------------我是华丽的分割线(●ˇ\forall ˇ●)-----------------------$

$看上去很难吧??$做起来也很难

$Ⅰ.考虑最小$

$那请你先想个简单的问题，考虑两个叶子节点f最小值的情况。很容易想到我在路上全挂满1对吧?$

$但问题来了，如果两个叶子间的距离为奇数，就行不通了。这时候最小值怎么算呢?$

$全放1肯定不行，少放1个1也不行，这样要抵消成0的话还是要放1.$

$那就少放两个1,让这连个数异或后可以抵消掉1，这样并不难$

$Ⅱ.考虑最大$

$这个似乎就很难了。但是一开始肯定希望把路上放满不同的数，这样肯定可以异或成0.$

$为什么?回想一下异或的性质，我是不是可以这样放权值$

$0000001,0000010,0000100,0001000......突然到最后，放一个11111111和前面全部抵消$

$完美!!这样我们的答案就是n-1!!不过用脚想也知道没这么简单。什么时候不满足呢?$

$当叶子节点距离只有2的时候无法满足，2是XOR的特殊情况，想为0就必须放两个相同的。$

#include 
   
    using namespace std;const int maxn=2e5+5;struct p{	int to,nxt;}d[maxn];int n,head[maxn],cnt=1;void add(int u,int v){	d[cnt].nxt=head[u],d[cnt].to=v,head[u]=cnt++;}int indug[maxn],deep[maxn],ji,ou,father[maxn];void dfs(int u,int fa){	deep[u]=deep[fa]+1;	if(indug[u]==1)	{		if(deep[u]%2)	ji=1;		else	ou=1;		father[fa]++;		return;	}	for(int i=head[u];i;i=d[i].nxt)		if(d[i].to!=fa)	dfs(d[i].to,u);}int main(){	cin>>n;	for(int i=1;i
    
     >l>>r;		add(l,r);add(r,l);		indug[l]++,indug[r]++;	}	int root;	for(int i=1;i<=n;i++)	if(indug[i]!=1)	root=i;//随便找一个不是叶子的节点为根	dfs(root,root); 	if(ji&&ou)	cout<<3<<" ";	else	cout<<1<<" ";	int ans=n-1;	for(int i=1;i<=n;i++)		if(father[i])	ans=ans-father[i]+1;	cout<
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/105809348 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！