class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回符合题意的最长的子串长度
     * @param x string字符串 
     * @return int整型
     */
    int Maximumlength(string x) {
        // write code here
        int ans=0,ln=-1,lp=-1,ly=-1,l=x.length(),te;
        for(int i = 0; i < l; ++i){
            if (x[i]=='n') ln=i;
            if (x[i]=='p') lp=i;
            if (x[i]=='y') ly=i;
            te=i-min(ln,min(lp,ly));
            if (te>ans) ans=te;
        }
        return ans;
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 给定一个后缀表达式，返回它的结果
     * @param str string字符串 
     * @return long长整型
     */
    long long d[1100000];
    char c[1100000];
    int dt,ct;
    long long solve(string s) {
        // write code here
        int l=s.length();
        long long num=0;
        dt=ct=0;
        for(int i = 0; i < l; ++i){
            if (s[i]>='0'&&s[i]<='9'){
                num=num*10+(s[i]-'0');
                continue;
            }
            if (s[i]=='#'){
                d[++dt]=num;
                num=0;
                continue;
            }
            if (s[i]=='+'){
                d[dt-1]+=d[dt];
                --dt;
            }else if (s[i]=='-'){
                d[dt-1]-=d[dt];
                --dt;
            }else{
                d[dt-1]*=d[dt];
                --dt;
            }
        }
        return d[1];
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param e int整型vector 长度为n-1的数组，表示结点2到结点n的父结点
     * @return int整型
     */
    int n,ma,num,f[110000][2];
    vector<int> v[110000];
    void upd(int x){
        if (x>ma){
            ma=x;
            num=1;
        }else if (x==ma){
            num++;
        }
    }
    void dfs(int x,int fa){
        f[x][0]=0;f[x][1]=-n*2;
        for(int y:v[x]) if (y!=fa){
            dfs(y,x);
            int te=f[y][0]+1;
            if (te>f[x][0]){
                f[x][1]=f[x][0];
                f[x][0]=te;
            }else if (te>f[x][1])
                f[x][1]=te;
            te=f[y][1]+1;
            if (te>f[x][0]){
                f[x][1]=f[x][0];
                f[x][0]=te;
            }else if (te>f[x][1])
                f[x][1]=te;
        }
        upd(f[x][0]);
        upd(f[x][1]);
        int sm1=-1,sm2=-1;
        for(int y:v[x]) if (y!=fa){
            if (sm1==-1){
                sm1=f[y][0];
                sm2=f[y][1];
                continue;
            }
            upd(f[y][0]+sm1+2);
            upd(f[y][0]+sm2+2);
            upd(f[y][1]+sm1+2);
            upd(f[y][1]+sm2+2);
            if (f[y][0]>sm1){
                sm2=sm1;
                sm1=f[y][0];
            }else if (f[y][0]>sm2)
                sm2=f[y][0];
            if (f[y][1]>sm1){
                sm2=sm1;
                sm1=f[y][1];
            }else if (f[y][1]>sm2)
                sm2=f[y][1];           
        }
    }
    int tree3(vector<int>& e) {
        // write code here
        ma=0;num=1;
        n=e.size()+1;
        for(int i=1;i<=n;++i) v[i].clear();
        for(int i=2;i<=n;++i){
            v[e[i-2]].push_back(i);
        }
        dfs(1,0);
        if (num==1) return ma-1;else return ma;
    }
};