Edge Weight Assignment

​​D - Edge Weight Assignment​​

參考：​​Codeforces Round #633 Editorial ​​

感覺這個題關鍵之處在于，要會将圖化為一棵樹，這樣邏輯會清晰很多。

如果葉子之間距離存在有奇數（非1），那麼最小的 f 值一定為3，否則為1。可以通過求解其他葉子節點到某一個葉子節點的距離得出，得出的結論對任何一個節點都成立（即如果該節點滿足，那麼其他節點也滿足）。

另一個很重要的結論就是如果存在一個父節點連接配接兩個葉子節點的情況的話，那麼 f 的最大值需要減1，因為葉子節點的值已确定，不可能再有别的變化。

// Created by CAD on 2020/4/13.
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
vector<int> e[maxn];
bool bj=0;
void dfs(int u,int fa=0,int x=0){
    for(auto i:e[u])
        if(i!=fa) dfs(i,u,x^1);
    if(e[u].size()==1&&x) bj=1;
}
int vis[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
//    FOPEN;
    int n;cin>>n;
    for(int i=1,x,y;i<=n-1;++i)
        cin>>x>>y,e[x].push_back(y),e[y].push_back(x);
    for(int i=1;i<=n;++i)
        if(e[i].size()==1){
            dfs(i);break;
        }
    int ans=n-1;
    for(int i=1;i<=n;++i)
        if(e[i].size()==1)
            ans-=vis[e[i][0]],vis[e[i][0]]=1;
    cout<<(bj?3:1)<<" "<<ans<<"\n";
    return 0;
}