luogu5290 春节十二响
程序员文章站
2022-03-13 17:17:12
思路
**先考虑一条链的情况怎么做。**
因为只有两个子树,并且两个子树都是链。所以可以把这两条链找出来,然后$sort$一下。合并起来。
**然后推广到树上**
对于每一棵树都可以按照和上面同样的方法合并成一条链。 ......
思路
先考虑一条链的情况怎么做。
因为只有两个子树,并且两个子树都是链。所以可以把这两条链找出来,然后\(sort\)一下。合并起来。
然后推广到树上
对于每一棵树都可以按照和上面同样的方法合并成一条链。
这样就可以\(o(n^2logn)\)做了。
考场上就想到这些。而且链的情况还忘了存档。。。
启发式合并
只要对于每个节点维护出一个堆,并且进行启发式合并。就可以达到\(o(nlogn)\)的复杂度了。
还是太菜了。。。
代码
/* * @author: wxyww * @date: 2019-04-11 20:14:14 * @last modified time: 2019-04-11 20:23:59 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int n = 200000 + 100; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } priority_queue<int>q[n]; vector<int>e[n]; int a[n],dy[n]; int tmp[n]; int merge(int x,int y) { if(q[x].size() < q[y].size()) swap(x,y); int js = 0; while(!q[y].empty()) { tmp[++js] = max(q[y].top(),q[x].top()); q[y].pop();q[x].pop(); } for(int i = 1;i <= js;++i) q[x].push(tmp[i]); return x; } void dfs(int u) { int k = e[u].size(); dy[u] = u; for(int i = 0;i < k;++i) { int v = e[u][i]; dfs(v); dy[u] = merge(dy[u],dy[v]); } q[dy[u]].push(a[u]); } int main() { int n = read(); for(int i = 1;i <= n;++i) a[i] = read(); for(int i = 2;i <= n;++i) e[read()].push_back(i); dfs(1); ll ans = 0; while(!q[dy[1]].empty()) { ans += q[dy[1]].top();q[dy[1]].pop(); } cout<<ans; return 0; }
上一篇: 上帝会提供的
下一篇: JavaScript 数组的方法(二)