1 条题解

  • 0
    @ 2024-2-25 20:51:54
    #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;
    }
    
    

    信息

    ID
    210
    时间
    4000ms
    内存
    2048MiB
    难度
    10
    标签
    (无)
    递交数
    19
    已通过
    1
    上传者