[Codeforces 100365I][ASC 34]Tour

這題目不好找，附個題目連結

此題轉換成圖論模型就是，給你一棵樹，求最少要加幾條邊才有一條路徑，經過每個點恰好一次並回到原點？

仔細思考，可以發現，這題等價求這棵樹最少可以分解成多少條鏈
舉幾個例子，就會發現分解成幾條鏈，就是要多建幾條路，把這些鏈連接成一個經過每個點恰好一次的環

因此，要怎麼求一棵樹最少分解成幾條鏈呢？

可以考慮樹形$DP$
$DP_{0}[u]$代表以$u$為根結點的這棵子樹至少分解成幾條鏈
$DP_{1}[u]$代表「根結點為某條鏈的自由端」的情況下，以$u$為根結點的這棵子樹至少分解成幾條鏈

要計算$DP_{0}[u]$時，有以下三種情況，取最佳解即可：

要計算$DP_{1}[u]$時，有以下兩種情況，取最佳解即可：

如果圖解還是看不懂怎麼遞迴計算$DP_{0}[u]$和$DP_{1}[u]$，請留言問問題或參考code吧~

時間複雜度：$O(N\log N+M)$ (使用$O(1)$取前2小值的算法可以去掉那個$\log$)

p.s. 這題不是直接讀標準輸入輸出，要使用讀寫檔案的方式，所以code裡面的freopen不是忘記註解掉，請特別注意！第一次遇到不是標準輸入輸出的題目，莫名WA半天找不到bug...... Orz

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
using namespace std;
int N,DP[100000][2];
vector<int>ET[100000];
bool VIS[100000];
void Dfs(const int u,const int fa)
{
    assert(!VIS[u]);
    VIS[u]=true;
    DP[u][0]=DP[u][1]=0;
    vector<int>s;
    for(const int nxt:ET[u])if(nxt!=fa)
    {
        Dfs(nxt,u);
        s.push_back(DP[nxt][1]-DP[nxt][0]);
        DP[u][0]+=DP[nxt][0],DP[u][1]+=DP[nxt][0];
    }
    sort(s.begin(),s.end());
    if(s.empty())DP[u][0]++;
    else if((int)s.size()==1)DP[u][0]+=min(s[0]+1,1);
    else if((int)s.size()>=2)DP[u][0]+=min(min(s[0]+1,(s[0]+s[1])+1),1);
    else assert(0);
    if(!s.empty())DP[u][1]+=min(s[0],0);
}
int main()
{
    freopen("tour.in","r",stdin);
    freopen("tour.out","w",stdout);
    while(scanf("%d",&N)==1)
    {
        for(int i=0;i<N;i++)ET[i].clear(),VIS[i]=false;
        for(int i=0,a,b;i<N-1;i++)scanf("%d%d",&a,&b),a--,b--,ET[a].push_back(b),ET[b].push_back(a);
        Dfs(0,-1);
        for(int i=0;i<N;i++)assert(VIS[i]); 
        printf("%d\n",DP[0][0]);
        break;
    }
    return 0;
}