Category: 数据结构

相关链接

题目传送门：http://uoj.ac/problem/284
数据生成器：http://paste.ubuntu.com/23987506/
官方题解：http://vfleaking.blog.uoj.ac/blog/2292

解题报告

这题有一点不想写题解 _(:з」∠)_
UOJ的官方题解还是很清楚的吧？
那就偷懒不写辣！

值得一提的是，这题也是用链剖来强行优化复杂度
这个优化技巧已经多次在各种比赛中出现了
很多复杂度跟深度有关的题目都可以拿这货优化

另外，scPointer好劲啊！
都给UOJ出题了！
scPointer是我榜样！

Code

这份代码多了一个$log$
问题不是在链剖那里，而是线段树那里偷懒，多了一个二分

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300000+9;
const int M = 19;

int n,m,tot,head[N],to[N],nxt[N],sz[N],pos[N];
int fa[N][M],val[N][M],hvy[N],dep[N],Val[N];
vector<pair<int,int> > q[N];
LL vout[N],sum[N];

class Segment_Tree{
	int tag[N<<2],cnt;
	LL sum[N<<2],ans_tmp;
	public:
		inline void modify(int l, int r, int v) {
			modify(1, 1, n, l, r, v);
		}
		inline int query(int p) {
			query(1, 1, n, p);
			return ans_tmp;
		}
		inline LL GetSum(int l, int r) {
			ans_tmp = 0;
			GetSum(1, 1, n, l, r);
			return ans_tmp;
		}
	private:
		void push_down(int w, int l, int r) {
			tag[w<<1] = tag[(w<<1)+1] = tag[w];
			int mid = l + r + 1 >> 1;
			sum[w<<1] = (LL)(mid - l) * tag[w];
			sum[(w<<1)+1] = (LL)(r -mid + 1) * tag[w];
			tag[w] = 0;
		}
		void modify(int w, int l, int r, int L, int R, int v) {
			if (L <= l && r <= R) {
				tag[w] = v;
				sum[w] = (LL)(r - l + 1) * v; 
			} else {
				if (tag[w]) push_down(w, l, r);
				int mid = l + r + 1 >> 1;
				if (L < mid) modify(w<<1, l, mid-1, L, R, v);
				if (mid <= R) modify((w<<1)+1, mid, r, L, R, v);
				sum[w] = sum[w<<1] + sum[(w<<1)+1]; 
			}
		}
		void query(int w, int l, int r, int p) {
			if (tag[w] || l == r) {
				ans_tmp = tag[w];
				return;
			} else {
				int mid = l + r + 1 >> 1;
				if (p < mid) query(w<<1, l, mid - 1, p);
				else query((w<<1)+1, mid, r, p);
			}
		}	
		void GetSum(int w, int l, int r, int L, int R) {
			if (L <= l && r <= R) {
				ans_tmp += sum[w];
			} else {
				if (tag[w]) push_down(w, l, r);
				int mid = l + r + 1 >> 1;
				if (L < mid) GetSum(w<<1, l, mid-1, L, R);
				if (mid <= R) GetSum((w<<1)+1, mid, r, L, R);
			}
		}
}SEG;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void Add_Edge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
}

void DFS1(int w, int f) {
	sz[w] = 1; fa[w][0] = f; 
	dep[w] = dep[f] + 1;
	val[w][0] = Val[f];
	for (int i=head[w];i;i=nxt[i]) {
		DFS1(to[i], w);
		sz[w] = max(sz[w], sz[to[i]] + 1);
		if (sz[hvy[w]] < sz[to[i]]) 
			hvy[w] = to[i];
	}
}

inline int query(int x, int y) {
	int ret = 0; x = dep[x]; 
	for (int j=M-1;~j;j--) {
		if (dep[fa[y][j]] > x) {
			ret = max(ret, val[y][j]);
			y = fa[y][j];
		}  
	} 
	return ret;
}

inline int find(int l, int r, int v) {
	int ret = l, mid;
	while (l <= r) {
		mid = l + r >> 1; 
		if (SEG.query(mid) < v) ret = mid, l = mid + 1;
		else r = mid - 1;
	} 
	return ret + 1;
}

void DFS2(int w) {
	pos[w] = ++tot;
	if (hvy[w]) DFS2(hvy[w]);
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != hvy[w]) {
			DFS2(to[i]);
		}
	} 
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != hvy[w]) {
			for (int j=0,p,v;j<sz[to[i]];j++) {
				v = SEG.query(pos[to[i]]+j);
				if (SEG.query(pos[w]+j+1) >= v) continue;
				p = find(pos[w]+j-1, pos[w]+sz[w]-1, v); 
				SEG.modify(pos[w]+j+1, p-1, v);
			}
		}
	}
	for (int i=0,lim=q[w].size(),t,id,mx,p;i<lim;i++) {
		t = q[w][i].first; id = q[w][i].second;
		mx = query(w, t); 
		p = find(pos[w], pos[w]+sz[w]-1, mx) - pos[w]; 
		vout[id] = (LL)p * mx - (p?SEG.GetSum(pos[w], pos[w]+p-1):0LL) + dep[t] - dep[w];
	}
	int p = find(pos[w], pos[w]+sz[w]-1, Val[w]);
	SEG.modify(pos[w], p-1, Val[w]);
}

int main() {
	n = read();
	for (int i=1;i<=n;i++) Val[i] = read();
	for (int i=2;i<=n;i++) Add_Edge(read(), i);
	m = read();
	for (int i=1,s,t;i<=m;i++) {
		s = read(); t = read();
		q[s].push_back(make_pair(t, i));
	}
	DFS1(1, 1);
	for (int j=1;j<M;j++) {
		for (int i=1;i<=n;i++) {
			fa[i][j] = fa[fa[i][j-1]][j-1];
			val[i][j] = max(val[i][j-1],val[fa[i][j-1]][j-1]);
		}
	}
	DFS2(1);
	for (int i=1;i<=m;i++) 
		printf("%lld\n",vout[i]);
	return 0;
}

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4712
神犇题解Ⅰ：http://www.cnblogs.com/clrs97/p/6006305.html
神犇题解Ⅱ：http://blog.csdn.net/lych_cys/article/details/53454323

解题报告

考虑每一个节点保存三个值

1. $w(i)$ 表示第i个点自己的权值
2. $f(i) = \sum\limits_{j \in son(i)} {d(j)} $
3. $d(i) = \min (w(i),f(i))$

显然 $d(i)$ 就是答案
于是我们只需要考虑维护 $f(i)$ 即可

考虑每一次修改操作
其一定是改变了到根节点的路径上连续一个区间的 $f(i)$
这个连续的区间满足 $f(i) + delta < w(i)$ 于是可以直接用树链剖分搞区间加就可以了

现在考虑复杂度：

因为 $f(i)$ 是不减的，所以如果一个点的 $f(i)$ 大于了 $w(i)$ 那么便会一直大下去
初始每一个点会贡献一次暴力修改，每一次修改操作也会贡献一次暴力修改

于是均摊下来，单次操作的暴力修改次数就是 $O(1)$ 的了
于是总复杂度：$O((n+m)log^2n)$