1 条题解
-
0
#include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; template<typename T> inline void read(T &x) { x = 0; char a = getchar(); bool f = 0; for(; ! isdigit(a); a = getchar()) if(a == '-') f = 1; for(; isdigit(a); a = getchar()) x = x * 10 + a - '0'; if(f) x = -x; } #define lep(i, l, r) for(int i = (l); i <= (r); i ++) #define rep(i, l, r) for(int i = (r); i >= (l); i --) const int N = 1e6 + 10; const ll Lim = 1e13; int n, m; struct BIT { ll c[N]; #define lowbit(x) (x & -x) void upd(int x, ll v) { for(; x <= n; x += lowbit(x)) c[x] += v; } ll ask(int x) { ll res = 0; for(; x; x -= lowbit(x)) res += c[x]; return res; } ll qry(int l, int r) { return ask(r) - ask(l - 1); } } c1, c2; int Fa[N]; inline int find(int x) { return x == Fa[x] ? x : Fa[x] = find(Fa[x]); } int fa[N]; vector<int> e[N]; struct Qry { int id, x; ll v; } q[N]; ll val[N]; int dfn[N], sz[N]; void dfs(int x) { dfn[x] = ++ dfn[0]; sz[x] = 1; for(int y : e[x]) dfs(y), sz[x] += sz[y]; } void modify(int x, int y, ll v, int tv) { c1.upd(dfn[x], v); c2.upd(dfn[x], tv); y = fa[y]; if(y) { c1.upd(dfn[y], -v); c2.upd(dfn[y], -tv); } } struct Node { ll v; int x; Node() {} Node(ll _v, int _x) : v(_v), x(_x) {} inline bool operator <(const Node &t) const { return v != t.v ? v > t.v : x < t.x; } inline bool operator ==(const Node &t) const { return v == t.v && x == t.x; } } ; struct Queue { priority_queue<Node> q1, q2; void push(Node v) { q1.push(v); } void erase(Node v) { q2.push(v); } Node top() { while(q1.size() && q2.size() && q1.top() == q2.top()) q1.pop(), q2.pop(); return q1.top(); } inline int size() { return q1.size() - q2.size(); } } Q; ll ans[N]; void link(int x) { ll sum = c1.qry(dfn[x], dfn[x] + sz[x] - 1); int ssz = c2.qry(dfn[x], dfn[x] + sz[x] - 1); int t = find(fa[x]); modify(fa[x], t, sum, ssz); Fa[x] = t; if(t != 1) { Q.push( Node( ceil (1.0 * (- c1.qry(dfn[t], dfn[t] + sz[t] - 1)) / c2.qry(dfn[t], dfn[t] + sz[t] - 1) + 1e-9), t ) ); } } int main() { read(n); read(m); lep (i, 2, n) read(fa[i]), e[fa[i]].push_back(i); lep (i, 1, n) read(val[i]); lep (i, 1, m) { read(q[i].x); read(q[i].v); q[i].id = i; } lep (i, 1, n) val[i] -= Lim; dfs(1); lep (i, 1, n) Fa[i] = i, modify(i, i, val[i], 1); lep (i, 1, m) q[i].v += Lim; sort(q + 1, q + 1 + m, [] (Qry a, Qry b) { return a.v < b.v; } ); lep (i, 2, n) { Q.push( Node(- val[i] / 1, i) ); } lep (i, 1, m) { while(Q.size() && Q.top().v <= q[i].v) { Node tmp = Q.top(); int fx = fa[tmp.x]; Q.erase(tmp); fx = find(fx); if(fx != 1) { Q.erase( Node( ceil (1.0 * (- c1.qry(dfn[fx], dfn[fx] + sz[fx] - 1)) / c2.qry(dfn[fx], dfn[fx] + sz[fx] - 1) + 1e-9), fx ) ); } link(tmp.x); } ans[q[i].id] = c1.qry(dfn[q[i].x], dfn[q[i].x] + sz[q[i].x] - 1) + c2.qry(dfn[q[i].x], dfn[q[i].x] + sz[q[i].x] - 1) * q[i].v; } lep (i, 1, m) printf("%lld\n", ans[i]); return 0; }
- 1
信息
- ID
- 210
- 时间
- 4000ms
- 内存
- 2048MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 22
- 已通过
- 1
- 上传者