C++ 中构造函数可以声明为虚函数，从而实现运行时多态。

通过指向 Base 的指针删除 Derived 对象时，一定会先调用 Derived 的析构函数，再调用 Base 的析构函数。

在 C++ STL 中，stack 的 pop() 函数会返回栈顶元素并将其删除。

树上漫步

小A有一棵n个结点的树，这些结点依次以1~n标号。小A想在这棵树上漫步。具体来说，小A会从树上的某个结点出发，每一步可以移动到与当前结点相邻的结点，并且小A只会在偶数步（可以是零步）后结束漫步。现在小A想知道，对于树上的每个结点，从这个结点出发开始漫步，经过偶数步能结束漫步的结点有多少个（可以经过重复的节点）。

第一行，一个正整数n。
接下来n-1行，每行两个整数u,v，表示树上有连接结点u和结点v的边。

一行，n个整数，第i个整数表示从结点i出发开始漫步，能结束漫步的结点数量。

【样例输入1】

3
1 3
2 3
【样例输出1】

2 2 1
对于所有测试点，保证1≤n≤2×10^5。

环线

小A喜欢坐地铁。地铁环线有n个车站，依次以1~n标号。车站i(i<n)的下一个车站是车站i+1。特殊地，车站n的下一个车站是车站1。小A会从某个车站出发，乘坐地铁环线到某个车站结束行程，这意味着小A至少会经过一个车站。小A不会经过一个车站多次。当小A乘坐地铁环线经过车站i时，小A会获得a_i点快乐值。请你安排小A的行程，选择出发车站与结束车站，使得获得的快乐值总和最大。

第一行，一个正整数n，表示车站的数量。
第二行，n个整数a_i，分别表示经过每个车站时获得的快乐值。

一行，一个整数，表示小A能获得的最大快乐值。

【样例输入1】

4
-1 2 3 0
【样例输出1】

5
对于所有测试点，保证1≤n≤2×10^5，-10^9≤a_i≤10^9。