第1题
【题目大意】
给出一棵有根树,每条边有一个通过时间。你可以进行一次“操作”,使得某条边的通过时间增加一秒。
你需要让根节点到每个叶节点的所需时间都相等,且“操作”次数最少。
叶节点被定义为除根节点外所有只与一个点相连的节点。
【数据输入】
第一行一个正整数N,表示树上的节点个数。
第二行一个正整数S,表示根节点的编号。
接下来N-1行每行三个数a[i],b[i]和t[i],表示第i条边连接节点a[i]和b[i],通过时间为t[i]。
【数据输出】
输出一行一个非负整数,表示最小“操作”次数。
【样例输入】
3
1
1 2 1
1 3 3
【样例输出】
2
【样例解释】
对第一条边进行两次“操作”即可。
【数据范围】
对于30%的数据,n<=5,答案不超过10
对于60%的数据,n<=5000
对于100%的数据,n<=5*10^6,t[i]<=10^6
第2题
【题目大意】
狐狸来到了葡萄架下,葡萄架下有一排n串葡萄,他想将一部分葡萄偷走。
每个葡萄都有一个美味值,当然因为葡萄有甜有酸,美味值也有正有负。
为了不让农夫发现,狐狸决定,每连续的k串葡萄中,最多偷走b串,但是由于狐狸太贪心,所以每连续的k串葡萄中,它最少偷走a串。
由于狐狸对农夫怀恨在心,它希望自己偷走的葡萄的美味值总和减掉剩余的葡萄的美味值总和最大。请你帮助它求出这个最大值。
【数据输入】
第一行四个空格分隔的非负整数n,k,a,b,含义如题所示。
接下来一行n个空格分隔的整数,代表每串葡萄的美味值。
【数据输出】
输出一行一个整数,表示偷走的葡萄美味值总和减掉剩余的葡萄的美味值总和的最大值。
【样例输入】
2 1 0 1
2 -2
【样例输出】
4
【样例解释】
偷走第一串葡萄即可。
【数据范围】
对于10%的数据,n<=10
对于另外30%的数据,a=0,b=k
对于100%的数据,n<=10^4,0<=a<=b<=k<=10
【题目大意】
给出一棵有根树,每条边有一个通过时间。你可以进行一次“操作”,使得某条边的通过时间增加一秒。
你需要让根节点到每个叶节点的所需时间都相等,且“操作”次数最少。
叶节点被定义为除根节点外所有只与一个点相连的节点。
【数据输入】
第一行一个正整数N,表示树上的节点个数。
第二行一个正整数S,表示根节点的编号。
接下来N-1行每行三个数a[i],b[i]和t[i],表示第i条边连接节点a[i]和b[i],通过时间为t[i]。
【数据输出】
输出一行一个非负整数,表示最小“操作”次数。
【样例输入】
3
1
1 2 1
1 3 3
【样例输出】
2
【样例解释】
对第一条边进行两次“操作”即可。
【数据范围】
对于30%的数据,n<=5,答案不超过10
对于60%的数据,n<=5000
对于100%的数据,n<=5*10^6,t[i]<=10^6
第2题
【题目大意】
狐狸来到了葡萄架下,葡萄架下有一排n串葡萄,他想将一部分葡萄偷走。
每个葡萄都有一个美味值,当然因为葡萄有甜有酸,美味值也有正有负。
为了不让农夫发现,狐狸决定,每连续的k串葡萄中,最多偷走b串,但是由于狐狸太贪心,所以每连续的k串葡萄中,它最少偷走a串。
由于狐狸对农夫怀恨在心,它希望自己偷走的葡萄的美味值总和减掉剩余的葡萄的美味值总和最大。请你帮助它求出这个最大值。
【数据输入】
第一行四个空格分隔的非负整数n,k,a,b,含义如题所示。
接下来一行n个空格分隔的整数,代表每串葡萄的美味值。
【数据输出】
输出一行一个整数,表示偷走的葡萄美味值总和减掉剩余的葡萄的美味值总和的最大值。
【样例输入】
2 1 0 1
2 -2
【样例输出】
4
【样例解释】
偷走第一串葡萄即可。
【数据范围】
对于10%的数据,n<=10
对于另外30%的数据,a=0,b=k
对于100%的数据,n<=10^4,0<=a<=b<=k<=10