[USACO17JAN] Promotion Counting P 题解

前言

好久没写题解了，今天趁我心情好赶紧水一篇。

思路

首先拿到这题，关键词检索：子树，比 \(p_i\) 大的，树状数组！现在考虑如何去掉其他子树的贡献……emm，我直接在算贡献的时候去掉其他子树的贡献不就好了！

当然，暴力去贡献复杂度肯定爆炸，这里考虑如何通过保留最多的信息来达到减少复杂度的目的。这里用了 DSU on Tree 的思想：保留重儿子的信息，而在递归完轻儿子后清空轻儿子的信息。每个点被再次遍历到，当且仅当它所在的子树大小翻倍。这样做复杂度是 \(O(n \log n)\) 的，套上树状数组的复杂度就是 \(O(n \log^2 n)\) 的。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+100;

int read() {
	int x = 0; char ch = getchar();
	while(ch<'0' || ch>'9') ch = getchar();
	while(ch>='0'&&ch<='9') x = x*10+(ch-48), ch = getchar();
	return x;
}
int n;
int lsh[N], a[N];
//dsu on tree?
int head[N], tot;
struct node {
	int nxt, to;
} edge[N<<1];
void add(int u, int v) {
	edge[++tot].nxt = head[u];
	edge[tot].to = v;
	head[u] = tot;
}

struct BIT {
	int tc[N];
	int lowbit(int x) {
		return x & (-x);
	}
	void insert(int pos, int val) {
//		printf("%d %d\n", pos, val);
		for(int i = pos; i<=n; i+=lowbit(i)) {
			tc[i]+=val;
		}
	}
	int query(int pos) {
		int ret = 0;
		for(int i = pos; i; i-=lowbit(i)) {
			ret+=tc[i];
		}
		return ret;
	}
}bt;
int siz[N], son[N];
void predfs(int u, int fath) {
	siz[u] = 1;
	for(int i = head[u]; i; i = edge[i].nxt) {
		int v = edge[i].to;
		if(v == fath) continue;
		predfs(v, u);
		siz[u]+=siz[v];
		if(siz[son[u]] < siz[v]) son[u] = v;
	}
}

int ans[N];
void pls(int u, int fath) {
	bt.insert(a[u], 1);
	for(int i = head[u]; i; i = edge[i].nxt) {
		int v = edge[i].to;
		if(v == fath) continue;
		pls(v, u);
	}
}
void del(int u, int fath) {
	bt.insert(a[u], -1);
	for(int i = head[u]; i; i = edge[i].nxt) {
		int v = edge[i].to;
		if(v == fath) continue;
		del(v, u);
	}
}
void dfs(int u, int fath, bool op) {
	for(int i = head[u], v; i; i = edge[i].nxt) {
		v = edge[i].to;
		if(v == fath || v == son[u]) continue;
		dfs(v, u, 1);
	}
	
	if(son[u]) dfs(son[u], u, 0);
	
	for(int i = head[u], v; i; i = edge[i].nxt) {
		v = edge[i].to;
		if(v == fath || v == son[u]) continue;
		pls(v, u); 
	}
	ans[u] = bt.query(n) - bt.query(a[u]);
	bt.insert(a[u], 1);
//	cout << u << " " << bt.query(n) << " " << bt.query(a[u]) << endl;
	if(op) del(u, fath);
}
int main() {
	n = read();
	for(int i = 1; i<=n; ++i) {
		a[i] = lsh[i] = read();
	}
	sort(lsh+1, lsh+n+1);
	for(int i = 1; i<=n; ++i) {
		a[i] = lower_bound(lsh+1, lsh+n+1, a[i])-lsh;
	}
	for(int i = 2; i<=n; ++i) {
		int u = read();
		add(u, i);
		add(i, u);
	}
	predfs(1, 0);
	dfs(1, 0, 0);
	for(int i = 1; i<=n; ++i) {
		printf("%d\n", ans[i]);
	}
	return 0;
}

后记：

后来翻题解发现自己完全是搞麻烦了。其实这个题在递归前后做个差就好……麻了。

完全不会捏