链接 https://codeforces.com/contest/1462/problem/E2 This is the hard version of this problem. The only difference between the easy and hard versions is the constraints on k and m. In this version of th
This way 题意: 给你一棵树,每条边权为1,f(x)表示点x到1的路径上权重和。 你可以增加一条边权为k的边,使得f(x)最大值最小。问你k在[1,n]时最大f(x)最小是多少。 题解: 我想着只搜一次,搜的时候维护上面距离当前点最远的点的距离。我感觉可以是树链剖分或者动态开点线段树,然后加一些骚操作,但是好累啊,想想都绝望,写写200行打底。 于是放弃了,还是看题解去。毕竟有段
题目 树是无环的连通无向图。加权树具有分配给每条边的权重。两个顶点之间的距离是连接它们的路径上的最小权重之和。 给定一棵具有 n 个顶点的加权树,每条边的权重为 1。将 d(v) 表示为顶点 1 和顶点 v 之间的距离。 如果可以在任意两个顶点 a 和 b (1≤a,b≤n) 之间临时添加一条权重为 x 的边,则令 f(x) 为 max{d(v),1<=v<=n} 的最小可能值。请注意,经过此操
有 n 个人,每个人有 mi 和 pi ,mi 代表着如果有 mi 个人投票给他,那么他就免费投票给他,否则你需要花费pi的代价来收买他。请问最少花费多少使得所有人都投他。 看到 m 数组的数据范围,m 数组作为数组下标应该是没得跑了,有贪心策略我们应该选择 pi 尽量少的那些人,但是同时要照顾到 m 数组。 因为要贿赂的总人数我们不知道,但借用优先队列(小根堆),将目前为止
A - Doremy's Paint 3 推公式得 b1=b3=b5=b7.... b2=b4=b6=b8... 所以如果只有一个数或者两个数且数量差小于等于1即可 #include<bits/stdc++.h>using namespace std;const int N = 2e5+10,mod=1000003;#define int long longtypedef lon