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

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

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

. 满二叉树

试题名称：满二叉树
时间限制：1.0 s
内存限制：512.0 MB
给定一棵包含 n 个结点的有根二叉树，结点依次以 1, 2, …, n 编号，根结点编号为 1。
对于结点 i，其左儿子的编号记为 li，右儿子编号记为 ri。特别地，如果左儿子不存在则 li = 0，如果右儿子不存在则 ri = 0。
树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有 n 棵子树中，有多少棵子树是满二叉树。
满二叉树是指所有叶子深度均相同，且除叶子外均有两个儿子的二叉树。
对于 40% 的测试点，保证 1 ≤ n ≤ 500。
对于所有测试点，保证 1 ≤ n ≤ 10^5。

第一行，一个正整数 n，表示有根二叉树结点数量。
接下来 n 行，每行两个非负整数 li, ri，表示结点 i 的左儿子编号和右儿子编号，整数之间以空格分隔。

输出一行，一个整数，表示所有子树中满二叉树的数量。

3
2 3
0 0
0 0

5
2 3
4 5
0 0
0 0
0 0

3

4

. 条形蛋糕

试题名称：条形蛋糕
时间限制：1.0 s
内存限制：512.0 MB
寒假到了，小杨同学打算找一份兼职，顺便体验一下打工人的生活。
小杨同学给一家蛋糕店发送了一份自己的简历，希望可以在寒假来这里帮忙。店长最近正好遇到了一个难题：店里每天会做一条长条蛋糕，但是不同长度的蛋糕块卖出的价格不同，应该怎么分才能卖得最多呢？
有趣的是店长曾经学习过计算机专业。他最近对动态规划算法很感兴趣，于是打算用这个问题考一考小杨同学，问题如下：
给定一条长度为 n 的长条蛋糕和一个价格表，该价格表表示长度为 i（i = 1, 2, …, n）的蛋糕块的价格为 Pi。求蛋糕的分割方案，使得总销售价格最大，注意蛋糕块的长度必须为整数。

第一行一个正整数 n（1 ≤ n ≤ 10^3），表示长条蛋糕的总长度。
第二行 n 个正整数 P1, P2, …, Pn（1 ≤ Pi ≤ 10^5），表示不同长度蛋糕块的价格。

一行一个正整数，表示最大总销售价格。

4
1 5 8 9

10
1 5 8 9 10 17 17 20 24 30

10

30

环线

小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。

树上漫步

小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。