88~91 pts 求卡常
查看原帖
88~91 pts 求卡常
362750
TernaryTree楼主2023/11/16 19:27
#include <bits/stdc++.h>
#define fs first
#define sc second

using namespace std;

struct ios {
    inline char read() {
        static const int inlen = 1 << 18 | 1;
        static char buf[inlen], *s, *t;
        return (s == t) && (t = (s = buf) + fread(buf, 1, inlen, stdin)), s == t ? -1 : *s++;
    }
    template<typename T> inline ios& operator>> (T &x) {
        static char c11, boo;
        for (c11 = read(), boo = 0; !isdigit(c11); c11 = read()) {
            if (c11 == -1) return *this;
            boo |= c11 == '-';
        }
        for (x = 0; isdigit(c11); c11 = read()) x = x * 10 + (c11 ^ '0');
        boo && (x = -x);
        return *this;
    }
} fin;

struct exios {
    template<typename _CharT, typename _Traits = char_traits<_CharT>>
    struct typ {
        typedef basic_ostream<_CharT, _Traits>& (* end) (basic_ostream<_CharT, _Traits>&);
    };

    template<typename T> friend exios &operator<<(exios &out, T num) {
        if (num < 0) putchar('-'), num = -num;
        if (num >= 10) out << num / 10;
        putchar(num % 10 + '0');
        return out;
    }

    friend exios &operator<<(exios &out, const char * s) { printf("%s", s); return out; }
    friend exios &operator<<(exios &out, string s) { cout << s; return out; }
    friend exios &operator<<(exios &out, typ<char>::end e) { puts(""); return out; }
} fout;

typedef long long ll;
typedef pair<ll, int> pii;
const int maxn = 1e6 + 10;
const ll inf = 1e15;

template<typename T>
struct BIT {
	int n;
	T tr[maxn];
	
	void add(int p, T x) {
		if (!p) return;
		while (p <= n) {
			tr[p] += x;
			p += (p & -p);
		}
	}
	
	T query(int p) {
		T y = 0;
		while (p) {
			y += tr[p];
			p -= (p & -p);
		}
		return y;
	}
};

struct query {
	int u, x;
};

int n, q, cnt;
int f[maxn];
int a[maxn];
query qs[maxn];
int b[maxn];
vector<int> qt[maxn];
vector<int> tr[maxn];
ll ans[maxn];
int fa[maxn];
set<pii> s;
BIT<int> siz;
BIT<ll> tot;
int sz[maxn];
ll tt[maxn];
int rsz[maxn], dfn[maxn], now;

int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

ll calc(ll x, ll y) {
	return ceil((double) x / y);
}

void dfs(int u) {
	dfn[u] = ++now;
	for (int v : tr[u]) dfs(v);
}

void update(int u) {
	int p = find(f[u]);
	fa[u] = p;
	if (p != 1) s.erase(s.find({calc(-tt[p], sz[p]), p}));
	sz[p] += sz[u];
	tt[p] += tt[u];
	if (p != 1) s.insert({calc(-tt[p], sz[p]), p});
	siz.add(dfn[f[u]], sz[u]), siz.add(dfn[f[p]], -sz[u]);
	tot.add(dfn[f[u]], tt[u]), tot.add(dfn[f[p]], -tt[u]);
	s.erase(s.find({calc(-tt[u], sz[u]), u}));
}

signed main() {
	fin >> n >> q;
	siz.n = tot.n = n;
	for (int i = 2; i <= n; i++) fin >> f[i], tr[f[i]].push_back(i);
	dfs(1);
	for (int i = 1; i <= n; i++) {
		fin >> a[i], fa[i] = i, rsz[i] = 1;
		siz.add(dfn[i], 1), siz.add(dfn[f[i]], -1);
		tot.add(dfn[i], a[i]), tot.add(dfn[f[i]], -a[i]);
		sz[i] = 1, tt[i] = a[i];
	}
	for (int i = n; i >= 2; i--) rsz[f[i]] += rsz[i];
	for (int i = 1; i <= q; i++) {
		fin >> qs[i].u >> qs[i].x;
		b[++cnt] = qs[i].x;
	}
	sort(b + 1, b + 1 + cnt);
	cnt = unique(b + 1, b + 1 + cnt) - b - 1;
	for (int i = 1; i <= q; i++) qt[lower_bound(b + 1, b + 1 + cnt, qs[i].x) - b].push_back(i);
	for (int i = 2; i <= n; i++) s.insert({-a[i], i});
	for (int i = 1; i <= cnt; i++) {
		int cur = b[i];
		while (s.size()) {
			if ((*s.begin()).fs > cur) break;
			int u = (*s.begin()).sc;
			update(u);
		}
		for (int j : qt[i]) ans[j] = (ll) (siz.query(dfn[qs[j].u] + rsz[qs[j].u] - 1) - siz.query(dfn[qs[j].u] - 1)) * (ll) qs[j].x + (tot.query(dfn[qs[j].u] + rsz[qs[j].u] - 1) - tot.query(dfn[qs[j].u] - 1));
	}
	for (int i = 1; i <= q; i++) fout << ans[i] << endl;
	return 0;
}

/*
P7897 [Ynoi2006] spxmcq
考虑离线,将询问按 x 排序。
建出所有有效转移边,构成一个森林。
一个点的值 f_u 即为 tot_u + siz_u * x
考虑一个最小的数 x 不能维持其森林形态,即 f_rt = tot_rt + siz_rt * x >= 0
即 x >= - tot_rt / siz_rt 
动态维护一个东西去做它,大概是 multiset?
然后配合上一个链加单点查的数据结构,随便 dfn 树状数组解决了?
*/

2023/11/16 19:27
加载中...