题目一
分身术（body）
【问题描述】
小 A 和 小 B 正在写作业。今天的作业共有 n 道题，对于第 i 道题，小 A 需要花费 ai的时间才能做
出，而小 B 则需要花费 bi的时间。因为作业实在是太多了，所以 小 A 决定今天只完成其中某一些，并
且被完成的题目编号是连续的。
为了快速完成所有题目，小 A 和 小 B 甚至学会了分身术，可以同时进行多道题目。
两人决定在写完作业后去吃水果。当小 B 完成今天所有的计划题目后，才会前往吃水果 ，但小 A 只
要自己的任意一个分身完成了分配的题目，就会立刻前往吃水果。也就是说，如果决定今天完成的题目
编号区间为[L,R] ，那么 小 A 前往吃水果的时间为 L与R之间的最小值，而 小 B 要在经过 L与R之间的最大值的时间后，才
会去吃水果。
而 小 A 只需要花费K 时间就能吃完所有的水果，小 A 想通过决定题目区间的方法，来吃完所有水
果，而不让小 B 吃到水果。同时她还想要自己写的题目总数尽可能少。你能帮她算出最少要写几道题
吗？
如果不存在这样一个规划方式，使得小 A 独享所有水果，请输出 So Sad! 。 
【输入格式】
第一行两个整数n ，K分别表示题目数量和小 A 吃完水果所需要的时间。
第二行 n个数，表示数列 ai。
第三行n 个数，表示数列 bi。
【输出格式】
 一行一个整数，表示小 A 最少要写多少题。或者输出 So Sad! 。 
【样例输入1】
5 10
8 7 14 8 3
4 2 5 8 2
【样例输出1】
So Sad!
【样例1解释】
显然无论如何选择区间，小 A 都无法吃到所有水果。
【样例输入2】
5 14
21 20 17 22 1
11 22 3 15 6
【样例输出2】
2
【样例2解释】
区间 [4,5] 是一个合法的解。
【数据范围及约定】
1<=n<=10^6,1<=ai,bi,k<=10^9；

题目2

种树（tree）

【问题描述】 小 A 喜欢种树。一天，她得到了一棵 n个点的树，其中节点 i重量为w[i] 。

在种树之前，小 A 需要用起重机把树吊起。由于她只有一台起重机，所 以她只能选择一个点作为受 力点。根据 小 A 所在世界的物理知识，吊起一棵树需要做的功为

$\sum_{i}^{n-1}(w[i]∗dis[i])$

，其中 dis[i]表示节点i 与受力点之间的距离（边 数）。

由于吊起这棵树的费用与所做的功正相关，所以 小 A 希望所做的功尽可能小。请你帮助她求出吊起 这棵树所做的功的最小值。

【输入格式】 第一行包含一个整数 ，表示树的点数。

第二行包含 n个整数 w[i]，表示节点i 的重量。

接下来的n-1 行中，每行包含两个数u ，v表示 u和v 两点之间有连边。

【输出格式】 一个整数，表示最小做功。

【样例输入1】

4

1 2 3 4

1 2

2 3

3 4

【样例输出1】

8

【样例输入2】

4

3 2 1 4

1 2

2 3

3 4

【样例输出2】

12

【数据范围及约定】

n<=2*10^5。w[i]<=10^8。1<=u,v<=n