题解 CF1338B 【Edge Weight Assignment】

gyh20 · 2020-04-13 12:16:17 · 题解

一道有趣的结论题。

先设置一个度不为 1 的点为根。

首先，题目满足的其实就是所有叶子节点到根路径的异或值相同。

考虑最小值，如果所有叶节点到根的路径长度奇偶性相同，那么直接全部填 1 即可，否则，全部选 1,2,3 即可（在没有连接叶节点的边上交错填 1,2 在叶子节点前的边填数使得权值相等即可），所以，答案为 1 或 3。

最大值其实也不难，因为我们填的数可以很大，所以对于每一个节点，如果存在到叶节点的路径则到叶节点的路径权值必须相等，其它的可以不等，所以可以树形 DP，记录是否存在叶节点即可，判叶子结点可以直接用度数是否为 1。

#include<bits/stdc++.h>
using namespace std;
#define re register
inline int read(){
    re int t=0,f=0;re char v=getchar();
    while(v<'0')f|=(v=='-'),v=getchar();
    while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
    return f?-t:t;
} 
int n,m,t,a[100002],mx,ans,cnt,du[200002],rt,dp[200002],num,head[200002];
struct edge{
    int to,next;
}e[200002];
inline void add(re int x,re int y){
    e[++cnt].to=y;
    e[cnt].next=head[x];
    head[x]=cnt;
}
inline int dfs(re int x,re int y,re int z){
    if(du[x]==1){
        ans+=z;
        ++num;dp[x]=-1;
        return 1;
    }dp[x]=0;re int nnn=0;
    for(re int i=head[x];i;i=e[i].next){
    if(e[i].to^y){

    nnn|=dfs(e[i].to,x,z^1),dp[x]+=dp[e[i].to]+1;}}
    if(nnn)++dp[x];
    return 0;
}
signed main(){
    n=read();
    for(re int i=1,x,y;i<n;++i){
        x=read();y=read();++du[x];++du[y];
        add(x,y);add(y,x);
    }
    for(re int i=1;i<=n;++i)if(du[i]>1)rt=i;
    dfs(rt,rt,1);
    printf("%d %d\n",ans%num?3:1,dp[rt]);
}