建德网站制作公司,制作流程图软件,html网页制作难吗,山东网站建设哪里有BZOJ#3252. 攻略
题目描述
Solution
有一个显然的 贪心#xff0c;每次选取一个到根的点权和最大的点xxx#xff0c;将答案加上xxx到根的路径的点权和#xff0c;并将xxx到根的路径上的点的权值清零。
可以使用DFS序线段树维护。 但完全没有这么麻烦。
容易发现每一次选…BZOJ#3252. 攻略
题目描述
Solution
有一个显然的 贪心每次选取一个到根的点权和最大的点xxx将答案加上xxx到根的路径的点权和并将xxx到根的路径上的点的权值清零。
可以使用DFS序线段树维护。 但完全没有这么麻烦。
容易发现每一次选择的到根的链从儿子跳到父亲的过程中会从某一个时刻开始一直贡献为0因为之前已经有一个链把上面的权值都清空了。如果我们丢弃掉上面一段权值和为0的链相当于每一条边会且仅会被包括在一条链上我们只需要每次贪心地选取权值和最大的链即可。
这一过程不就是长链剖分的过程吗
我们将点权和当做长链剖分的剖分条件将树剖分成若干个互不相交的链将这些链排序取最大的kkk条链即可。
时间复杂度O(n排序)O(n排序)O(n排序)
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN600005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
vectorll V,e[MAXN];
ll len[MAXN],a[MAXN],mx[MAXN],s[MAXN],ans0;
void dfs1(int x,int father)
{for (auto v:e[x]){if (vfather) continue;dfs1(v,x);if (len[v]len[x]) len[x]len[v],mx[x]v;}len[x]a[x];
}
void dfs2(int x,int top,int father)
{if (mx[x]) dfs2(mx[x],top,x);for (auto v:e[x]){if (vfather||vmx[x]) continue;dfs2(v,v,x);}if (topx) V.PB(len[x]);
}
int main()
{int nread(),kread();for (int i1;in;i) a[i]read();for (int i1;in;i) {int uread(),vread();e[u].PB(v);e[v].PB(u);}dfs1(1,0);dfs2(1,1,0);sort(V.begin(),V.end());
// for (auto v:V) printf(%lld\n,v);for (int i1;imin(k,(int)V.size());i) ansV[V.size()-i];printf(%lld\n,ans);return 0;
}
