[TIOJ 1239] 致命武器 Lethal Weapon

作法：

由大到小 check 是否有辦法把這顆樹切成好幾條這個長度的鍊，而顯然練的長度必須整除 n-1 才有辦法。而在 check 的過程就類似 HOJ 135 - 縫紉課 ，兩題都是要處理把樹分成好幾條鍊的問題，都可以用DP作。而注意到在DP的時候，一顆子樹對應的子問題是「是否能夠把這顆子樹的所有邊分成幾條長度L的鍊，並且剩下一條長度<L的鍊以子樹的根為其中一個端點」，而因為其實一顆子樹裡面的邊數就是他的 size 再 -1，所以不用特別記錄邊數。而在轉移的時候就是拿 x 和 L-x 配對，如果有大於一條不能配對的話這顆子樹就是失敗的，反之就是可以的。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+10 ;
 
int size[maxn] ;
vector<int> v[maxn] ;
bool vis[maxn] ;
 
bool dfs(int x,int num)
{
    vis[x]=1 ; size[x]=1 ;
    multiset<int> st ;
    for(auto i : v[x]) if(!vis[i])
    {
        if(!dfs(i,num)) return 0 ;
        size[x]+=size[i] ;
        if(size[i]%num) st.insert(size[i]%num) ;
    }
    if(st.size()<=1) return 1 ;
    if(x==1)
    {
        if(st.size()%2) return 0 ;
        while(!st.empty())
        {
            int t=*st.begin() ; st.erase(st.begin()) ;
            if(!st.count(num-t)) return 0 ;
            st.erase(st.find(num-t)) ;
        }
        return 1 ;
    }
 
    int cnt=0 ;
    while(st.size()>1)
    {
        int t=*st.begin() ; st.erase(st.begin()) ;
        if(!st.count(num-t)) cnt++ ;
        else st.erase(st.find(num-t)) ;
        if(cnt>1) return 0 ;
    }
    if(!st.empty()) cnt++ ;
    return cnt<=1 ;
}
 
bool check(int x)
{
    if(x<=2) return 1 ;
    memset(vis,0,sizeof(vis)) ;
    return dfs(1,x) ;
}
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<n;i++)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
    }
 
    for(int i=n-1;i>=1;i--) if(((n-1)%i==0) && check(i))
    {
        printf("%d\n",i) ;
        return 0 ;
    }
}