D. Edge Weight Assignment樹，猜結論

LINK

Examples
inputCopy
6
1 3
2 3
3 4
4 5
5 6
outputCopy
1 4
inputCopy
6
1 3
2 3
3 4
4 5
4 6
outputCopy
3 3
inputCopy
7
1 2
2 7
3 4
4 7
5 6
6 7
outputCopy
1 6
           

題意給你一棵樹，要你計算出一種符合條件的樹最多和最少的權值不同的邊的數量，條件是：對于任意的兩個葉子節點他們之間的路徑異或和等于0

根據樣例瞎猜QAQ

結論：如果存在兩個葉子節點的距離為奇數那麼最小的不同權值的邊的數目一定是3，否則是1（轉換一下就是對于任意一個點求其餘點的深度，對于葉子節點計錄下深度值是偶數或奇數的次數）；最多的不同權值的邊的數目 ，我們考慮對于兩個距離為2的葉子節點他們的邊權值值一定要是相同的，其他的邊可以不同，根據這個就很容易計算。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=200010;
 int in[N];
 int fa[N];
 int d1[N],d2[N];
vector<int>v[N]; 
void dfs(int x,int fa,int *d)
{
	d[x]=d[fa]+1;
	for(int i=0;i<v[x].size();i++)
	{
		if(v[x][i]==fa) continue;
	    dfs(v[x][i],x,d);
	}
}
int main()
{
	//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n;scanf("%d",&n);
	
	for(int i=1;i<n;i++)
	{int a,b;
		scanf("%d%d",&a,&b); 
		in[a]++;in[b]++;v[a].push_back(b);v[b].push_back(a);
	}
	for(int i=1;i<=n;i++)
	{
		if(in[i]==1)
		{
			fa[v[i][0]]++;
		}
	}d1[0]=0;
    dfs(1,0,d1);
    int ans=0;int a=0,b=0;map<int,int>mp; 
	for(int i=1;i<=n;i++)
	{
		if(in[i]==1) 
		{
			if(d1[i]%2) a++;
			else b++;
			if(fa[v[i][0]]==1) ans++;
			else
			{
				mp[v[i][0]]=1;
			} 
			continue;
		}
	ans++;
	}
	ans+=mp.size();int mn;
    if(a&&b) mn=3;
    else mn=1;
	printf("%d %d\n",mn,ans-1); 
}