首页 > 代码库 > bzoj4756
bzoj4756
http://www.lydsy.com/JudgeOnline/problem.php?id=4756
水题一枚。。。但是我写了一个小时。。。手贱打反查不出来。。。
就是每次线段树合并,先把自己的儿子都合并了, 最后和自己合并。。。
#include<bits/stdc++.h> using namespace std; const int N = 100010; vector<int> G[N]; int n, sum, cnt; int t[N], id[N], size[N * 20], lc[N * 20], rc[N * 20], ans[N], root[N * 20]; bool cp(int i, int j) { return t[i] < t[j]; } void update(int l, int r, int &x, int pos) { x = ++cnt; int mid = (l + r) >> 1; ++size[x]; if(l == r) return; if(pos <= mid) update(l, mid, lc[x], pos); else update(mid + 1, r, rc[x], pos); } int merge(int x, int y) { if(!x || !y) return x + y; sum += size[lc[x]] * size[rc[y]]; lc[x] = merge(lc[x], lc[y]); rc[x] = merge(rc[x], rc[y]); size[x] = size[lc[x]] + size[rc[x]]; return x; } void dfs(int u) { int last = 0; for(int i = 0; i < G[u].size(); ++i) { int v = G[u][i]; dfs(v); root[v] = merge(root[v], root[last]); last = v; } sum = 0; root[u] = merge(root[u], root[last]); ans[u] = sum; } int main() { scanf("%d", &n); for(int i = 1; i <= n; ++i) { scanf("%d", &t[i]); id[i] = i; } sort(id + 1, id + n + 1, cp); for(int i = 1; i <= n; ++i) t[id[i]] = t[id[i - 1]] + (t[id[i]] != t[id[i - 1]]); for(int i = 1; i <= n; ++i) update(1, n, root[i], t[i]); for(int i = 2; i <= n; ++i) { int x; scanf("%d", &x); G[x].push_back(i); } dfs(1); for(int i = 1; i <= n; ++i) printf("%d\n", ans[i]); return 0; }
bzoj4756
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。