时间限制： 1.0 秒

空间限制： 512 MB

题目描述

伸展树（Splay）是一种基于均摊的二叉树。与 AVL 树或者红黑树等其他适度平衡的树不同，任意合法形态的二叉树都是合法形态的伸展树。

现在给定一棵 $n$ 个点，编号为 $1\sim n$，初始状态以 $1$ 为根的二叉树。再给出 $q$ 次伸展操作，每次给定一个节点编号，将该节点伸展至树根。

你需要计算出初始状态以及每次伸展操作结束之后，所有节点的深度的总和（其中根节点的深度为 $0$）。

输入格式

从标准输入读入数据。

第一行两个正整数 $n,q$，分别表示节点个数和伸展操作次数。

接下来 $n$ 行，每行两个非负整数。第 $i$ 行表示节点 $i$ 的左子节点和右子节点的编号，若为 $0$ 则代表无对应子节点。他们代表了二叉树的初始状态，其中保证 $1$ 一定为根。

接下来 $q$ 行，每行一个正整数，表示将对应编号的节点在当前状态下通过伸展操作伸展至根。

输出格式

输出到标准输出。

输出 $q+1$ 行，每行一个非负整数，表示初始状态以及每次伸展操作结束之后，所有节点的深度的总和。

8 2
2 3
6 4
5 7
0 8
0 0
0 0
0 0
0 0
2
7

13
15
21

样例 1 解释

两次伸展操作以及三种状态的节点深度总和计算见下方两个图。

第一次伸展操作只需要进行一次单旋操作即可，第二次伸展操作需要先看 7-3-1 的祖父-父亲-当前节点关系进行双旋操作（分别左旋 1 和 3），再做一次单旋操作，得到最终结果。

子任务

对于所有数据，保证 $n\le 2\times 10^5,q\le 10^5$。

本题无数据梯度，需要通过全部数据获得所有分数。

提示

对于子树所有节点深度的总和，我们给出以下 SplayNode 类作为示范，其中 pushup 可以更新子树的节点规模以及子树所有节点深度的总和。可以推算一下，对于两个子树添加一个父节点，通过这样的公式进行更新一定是正确的。

struct SplayNode
{
    SplayNode *fa;
    SplayNode *lc, *rc;
    int size;
    long long sum_dep;

    SplayNode(SplayNode *f = nullptr, SplayNode *l = nullptr, 
              SplayNode *r = nullptr, int s = 1, long long d = 0)
              : fa(f), lc(l), rc(r), size(s), sum_dep(d) {}
    void pushup()
    {
        size = 1, sum_dep = 0;
        if (lc) size += lc->size, sum_dep += lc->sum_dep;
        if (rc) size += rc->size, sum_dep += rc->sum_dep;
        sum_dep += (size - 1);
    }
};

你所需要做的，就是对于初始的二叉树通过一次遍历计算出初始状态各节点的子树规模和子树深度总和。以及实现伸展树的正确操作。

如果你对于左旋和右旋操作不会实现，可以参照本题所给出的白盒交互库进行实现，在此基础上实现自己的伸展功能。

来源

改编自 51nod 1854