网站搬家内页打不开,东莞seo网络营销策划,2019网页游戏排行榜,海口网站建设做网站传送门
题意#xff1a;给一棵nnn个点带点权的树#xff0c;要求把点分成若干部分#xff0c;有祖孙关系的点不能在同一部分。求每个部分最大值 的和 的最小值。 n≤2105n \leq 2\times 10^5n≤2105
由链的部分得到启发#xff0c;每个点用一个堆来维护#xff0c;合并两…传送门
题意给一棵nnn个点带点权的树要求把点分成若干部分有祖孙关系的点不能在同一部分。求每个部分最大值 的和 的最小值。
n≤2×105n \leq 2\times 10^5n≤2×105
由链的部分得到启发每个点用一个堆来维护合并两个时不断弹出两个堆顶并在最后加入较大值直到一个为空。合并完后加入根最终的和就是答案。
这样复杂为两边的大小之和。
发现合并是把较少的丢到较大的中可以启发式合并即少的取完后丢回较多的。可以用指针实现。
这样复杂度是O(nlogn)O(n\log n)O(nlogn)
好像和长链剖分本质相同
#include iostream
#include cstdio
#include cstring
#include cctype
#include queue
#include vector
#define MAXN 200005
using namespace std;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
typedef long long ll;
typedef priority_queueint pq;
pq *q[MAXN];
int val[MAXN];
vectorint e[MAXN];
void dfs(int u)
{q[u]new pq;for (int i0;i(int)e[u].size();i){dfs(e[u][i]);if (q[u]-size()q[e[u][i]]-size()) swap(q[u],q[e[u][i]]);vectorint tmp;while (!q[e[u][i]]-empty()) tmp.push_back(max(q[u]-top(),q[e[u][i]]-top())),q[u]-pop(),q[e[u][i]]-pop();for (vectorint::iterator ittmp.begin();it!tmp.end();it) q[u]-push(*it);}q[u]-push(val[u]);
}
int main()
{int nread();for (int i1;in;i) val[i]read();for (int i2;in;i) e[read()].push_back(i);dfs(1);ll ans0;while (!q[1]-empty()) ansq[1]-top(),q[1]-pop();printf(%lld\n,ans);return 0;
}
