POJ3437 Tree Grafting

我在做某题的时候看到有个多叉树转二叉树，就去学了下，看的这篇文章：https://blog.csdn.net/c20190102/article/details/69946551

然后就去找了这道题做，最开始想法是建了树以后转成二叉树然后再dfs得到深度，然后发现有点问题，因为链式前向星是逆序存边的，于是就改用临接表，然后t了很多发，不知道有多少组数据啊。

去看题解发现转成二叉树以后每个树的深度就变成了他父亲的深度+他是父亲的第几个儿子，然后就a了。

string s;
int fa[20005],ans,kase,deep[10005],cnt[10005];

inline void init()
{
    memset(fa,0,sizeof(fa));
    memset(cnt,0,sizeof(cnt));
}

int main()
{
    while (getline(cin,s))
    {
        init();
        if (s[0]=='#') break;
        int len=s.length();
        int now=1,pt=1,dep=0;
        ans=0;
        for (int i=0;i<len;i++)
        {
            if (s[i]=='u') 
            {
                now=fa[now];
                dep--;
            }
            else
            {
                pt++;
                dep++;
                ans=max(ans,dep);
                cnt[now]++;
                deep[pt]=deep[now]+cnt[now];
                fa[pt]=now;
                now=pt;
            }
        }
        printf("Tree %d: %d => ",++kase,ans);
        ans=0;
        for (int i=1;i<=pt;i++) ans=max(ans,deep[i]);
        printf("%d\n",ans);
    }
    return 0;
}