[TIOJ 1800] Color On a Tree

被這題雷了好久OAO
首先是他的第一個條件，其實指的是「對於一個點 x 相鄰的邊們，最多只允許有兩條邊的顏色相同」，如果照他寫的意思的話，當有兩條邊顏色相同，那就存在兩條邊滿足「找的到另一條也連到 x 根其顏色相同」了......
然後回答類型2指的是，一開始的樹只有根結點 1 ，然後每次輸入一個數就等於是加入一個新的節點，把他和他祖先的關係建好，這時候的到的樹，要輸出一次答案。
但是這題範例輸出雷人啦ˊˇˋ...... 第二個範測應該要再多輸出一個 2 才對=ㄦ=。

作法：

第一個觀察是如果有一條路徑上面都是同樣顏色的，而且他有先往上再往下，那麼可以把往下的那段改成其他顏色，不會影響結果。所以這樣等於是，如果 x 和 x 祖先之間的邊塗顏色 c ，那麼 x 到 x 孩子之間可以選一個讓他們之間也塗顏色 c ，而其他都塗不一樣的。而且任兩個子樹的結果不會互相影響。

所以就可以用DP作，設 dp[ x ] 代表以 x 為根的子樹中，x 到 x 祖先已經塗好一個顏色了，這顆子樹中的最佳解( 所以對根結點沒有定義 )。這樣可以得到轉移 ： dp[x] =
minimum of { max( dp[ s1 ] , dp[ s2 ]+1 , ... , dp[ sk ]+1 ) }。
其中 s1 代表的是他和 x 之間要被塗上 x 和 x 祖先之間的顏色，所以不用 +1 ，其他都 +1。而從這個式子也可以看出來那個 s1 應該要取 dp 值最大的會最好。

而題目要的是每次加入新的點都要輸出答案，所以沒辦法每次輸入一個點再重新DP一次。而只要注意到再多加一個點時影響的DP值只有他的祖先，而且如果要讓一個點的DP值到達 k ，那麼他的子孫個數會是 O( 2^k ) 的，反過來也就是說當一個節點的DP值 +1 了，那他的子孫們就他不多變兩倍了。由這件事就可以得到每次加入新結點時，被影響到DP值的節點不會超過 O(logn) 個，所以就可以一路更新上去，更新到DP值不變的時候馬上退出。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=300000+10 ;
int fa[maxn],dp[maxn] ;
int ma[maxn] ;
main()
{
    int type,n ; scanf("%d%d",&type,&n) ;
    fa[1]=1 ;
    int ans=0 ;
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&fa[i]) ; dp[i]=1 ;
        int x ;
        for(x=i; fa[x]!=1 && dp[x]>=ma[fa[x]] ;x=fa[x])
        {
            if(!ma[fa[x]]) { ma[fa[x]]=1 ; break ; }
            if(dp[x]==ma[fa[x]])
            {
                if(dp[fa[x]]==ma[fa[x]]) dp[fa[x]]++ ;
                else break ;
            }
            else
            {
                ma[fa[x]]=dp[x] ;
                if(dp[fa[x]]==dp[x]) break ;
                dp[fa[x]]=dp[x] ;
            }
        }
        if(fa[x]==1) ans=max(ans,dp[x]) ;
        if(type==2) printf("%d\n",ans) ;
    }
    printf("%d\n",ans) ;
}