D. Edge Weight Assignment
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
You have unweighted tree of n
vertices. You have to assign a positive weight to each edge so that the following condition would hold:
- For every two different leaves v1
and v2 of this tree, bitwise XOR of weights of all edges on the simple path between v1 and v2 has to be equal to 0
- .
Note that you can put very large positive integers (like 10(1010)
).
It's guaranteed that such assignment always exists under given constraints. Now let's define f
as the number of distinct weights in assignment.
In this example, assignment is valid, because bitwise XOR of all edge weights between every pair of leaves is 0
. f value is 2 here, because there are 2 distinct edge weights(4 and 5).
In this example, assignment is invalid, because bitwise XOR of all edge weights between vertex 1
and vertex 6 (3,4,5,4) is not 0
.
What are the minimum and the maximum possible values of f
for the given tree? Find and print both.
Input
The first line contains integer n
(3≤n≤105
) — the number of vertices in given tree.
The i
-th of the next n−1 lines contains two integers ai and bi (1≤ai<bi≤n) — it means there is an edge between ai and bi. It is guaranteed that given graph forms tree of n
vertices.
Output
Print two integers — the minimum and maximum possible value of f
can be made from valid assignment of given tree. Note that it's always possible to make an assignment under given constraints.
Examples
Input
Copy
(copy)
6
1 3
2 3
3 4
4 5
5 6
Output
Copy
(copy)
1 4
Input
Copy
(copy)
6
1 3
2 3
3 4
4 5
4 6
Output
Copy
(copy)
3 3
Input
Copy
(copy)
7
1 2
2 7
3 4
4 7
5 6
6 7
Output
Copy
(copy)
1 6
Note
In the first example, possible assignments for each minimum and maximum are described in picture below. Of course, there are multiple possible assignments for each minimum and maximum.
In the second example, possible assignments for each minimum and maximum are described in picture below. The f
value of valid assignment of this tree is always 3
.
In the third example, possible assignments for each minimum and maximum are described in picture below. Of course, there are multiple possible assignments for each minimum and maximum.
這題結論就是：
1.對于最小值，如果所有葉子節點距離兩兩都為偶數，最小值為1，否則為2
2.對于最大值，初始值為ans=n-1，如果一個節點有>=2個葉子節，那隻能都要合并成一個節點，即，如果某個節點有x個葉子節點，ans-=x-1；
代碼：
#include<stdio.h>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
#define ll long long
#define maxn 10500000
#include<vector>
/*struct node
{
int to,next;
}e[maxn];
int head[maxn],cnt=0;
void init()
{
memset(head,-1,sizeof(head));
}
void add(int u,int v)
{
e[cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt++;
}*/
vector<int>e[maxn];
void add(int u,int v)
{
e[u].push_back(v);
}
int a=0,b=0,ans=0,f=0,mp[maxn];
void dfs(int u,int fa,int now)
{
//printf("u=%d ans=%d a=%d b=%d\n",u,ans,a,b);
//printf("u=%d size=%d ans=%d a=%d b=%d\n",u,e[u].size(),ans,a,b);
if(e[u].size()==1)
{
if(now%2==0) a++;
else b++;
if(u==1)
{
if(mp[e[u][0]]==0) mp[e[u][0]]=1;
else ans--;
}
else
{
if(mp[fa]==0)
{
mp[fa]=1;
}
else ans--;
}
//printf(" u=%d mp[%d]=%d\n",u,fa,mp[fa]);
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
if(v==fa) continue;
//printf(" u(%d)=%d\n",v,u);
dfs(v,u,now+1);
}
}
else
{
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
if(v==fa) continue;
//printf(" u(%d)=%d\n",v,u);
dfs(v,u,now+1);
}
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d %d",&u,&v);
add(u,v);
add(v,u);
}
ans=n-1;
dfs(1,-1,0);
if(a>0&&b>0) printf("3 ");
else printf("1 ");
printf("%d\n",ans);
}