[蓝桥杯][2014年第五届真题]套娃

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int maxn = 1000010;
struct Node{
    int depth;
    vector<int>next;
    int pre;
}nodes[maxn];
int n,m;
void update(int index);
int main(void)
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        nodes[i].depth = 0;
        nodes[i].pre = i;
    }
    for(int i=0;i<n-1;i++)
    {
        int u,v;
        cin >> u >> v;
        nodes[v].pre = u;
        nodes[u].next.push_back(v);
    }
    
    for(int i=1;i<=n;i++)
    {
        int depth = 0,k=i;
        while(nodes[k].pre!=k)
        {
            depth++;
            k = nodes[k].pre;
        }
        nodes[i].depth = depth;
    }
    /* 
    cout << endl;
    for(int i=1;i<=n;i++)
    {
        cout << nodes[i].depth<<" ";
    }
    cout << endl;
    */ 
    for(int i=1;i<=m;i++)
    {
        string cm;
        int index;
        cin >> cm >> index;
        cout <<nodes[index].depth;
        if(i!=m) cout << endl;
        if(cm[0]==‘P‘)
        {
            if(nodes[index].depth==0)
            {
                
            }
            else
            {
                //将本节点和所有父节点保存 
                vector<int>father;
                int k = i;
                while(nodes[k].pre!=k)
                {
                    father.push_back(k);
                    int temp = k;
                    k = nodes[k].pre;
                    nodes[temp].pre = temp;
                }
                father.push_back(k);
                
                //从最上次的节点开始，进行更新，每次更新需要把自己的后继节点全部释放 
                int size = father.size();
                for(k=0;k<size;k++)
                {
                    update(father[size-1-k]);
                }
            }
        }
        /* 
        cout << endl;
        for(int k=1;k<=n;k++)
        {
            cout << nodes[k].depth<<" ";
        }
        cout << endl;
        */ 
    }
    return 0;
} 
void update(int index)
{
    queue<int>que;
    for(int i=0;i<nodes[index].next.size();i++)
    {
        que.push(nodes[index].next[i]);
    }
    nodes[index].next.clear();
    
    while(!que.empty())
    {
        int u = que.front(); que.pop();
        nodes[u].depth--;
        if(nodes[u].depth==0) nodes[u].pre = u;
        for(int i=0;i<nodes[u].next.size();i++)
        {
            que.push(nodes[u].next[i]);    
        } 
    }    
}