SDSC 2016 帮会控制

【题目描述】

树之大陆是一个有 n 座城市的王国(城市从 0 开始标号)。
城市之间有 n-1 条双向道路连接,使得每两座城市之间恰好存在一条道路。
城市 0 是首都。
初始时,每个城市都被一个单独的帮会控制。
村民在相邻的城市间移动,如果这两个城市不是隶属于同一个帮会,那么需
要付出一个单位的代价。
每一年都有新的帮会涌入首都,他们会扩张自己的势力范围。
具体说来,他们会占据从首都到 u 路径上的所有城市(包括首都和 u)。
因为这个原因,来往于城市间的代价变得捉摸不定。这让村民们很是苦恼,
于是他们找你来帮忙。
给定一个城市 u,定义 f(u)为以 u 为根的子树中所有节点到根节点的代价的
和。

【输入格式】

第一行一个整数 T 表示数据组数。
接下来 T 组数据,对于每组数据:
第一行有一个整数 n 表示城市的数目。
接下来 n-1 行每行两个整数 Ai,Bi 表示一条连接这两点的道路。
接下来一行一个整数 m,表示接下来有 m 组操作,每组操作包含一个字符 t
和一个整数 u。
如果 t=’O’,表示一个新的帮会占据了从首都到 u 路径上的城市。
如果 t=’q’,表示询问 f(u)。

【输出格式】

对于每组测试数据中的 t=’q’类型的询问,输出一行一个整数表示 f(u)。

【样例输入】

1
13
0 1
0 2
1 11
1 10
1 9
9 12
2 5
5 8
2 4
2 3
4 6
4 7
7
q 0
O 4
q 6
q 2
O 9
q 9
q 2

【样例输出】

26
1
6
1
13

【数据范围】

令 N 表示所有数据 n 的总和。
令 M 表示所有数据 m 的总和。
30%的数据,N、M≤1000
60%的数据,N、M≤50000
100%的数据,N、M≤200000

【题解】

这是一道良心的数据结构题。

我们发现访问一个点的操作类似于LCT中Access的操作,即根到u的路径全部变为实边。
于是我们用一颗LCT来维护实边/虚边,

虚边->实边时,整棵子树-1;
实边->虚边时,整棵子树+1。

我们利用DFS序,把子树操作转化为区间操作,用一颗支持区间修改,区间查询的线段树维护信息即可。

于是就能过了_(:зゝ∠)_。考场上蒟蒻自信没有对拍,TLE。原来变量名打错了。改对了之后也是WA,因为没有考虑到修改的节点应该是Splay上的深度最小的点。

所以说实现的时候要注意,修改整棵子树的时候要修改这棵子树的根,而在蒟蒻LCT的实现中,Splay维护的是一条偏爱链,所以这条链上的“根”是最小的那个点。也就是一直往左孩子走,直到不能走为止的点就是需要修改子树信息的点。

【代码】

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
const int N = 200005;
int n, fa[N];
LL ans;
char str[5];
namespace DFS {
	struct edge_type { int to, next; } edge[N << 1];
	int cnte, h[N], dep[N], tid[N], dfn[N], clo;
	void Init(int n) {
		for (int i = 1; i <= n; ++i) h[i] = 0;
		cnte = 1;
		clo = 0;
	}
	void ins(int x, int y) {
		edge[++cnte].to = y;
		edge[cnte].next = h[x];
		h[x] = cnte;
		edge[++cnte].to = x;
		edge[cnte].next = h[y];
		h[y] = cnte;
	}
	void dfs(int now, int father, int deep) {
		fa[now] = father;
		tid[now] = ++clo;
		dep[clo] = deep;
		for (int i = h[now]; i; i = edge[i].next)
			if (edge[i].to != father)
				dfs(edge[i].to, now, deep+1);
		dfn[now] = clo;
	}
}
namespace SGT {
	LL sum[N << 2], tag[N << 2];
	void build(int now, int l, int r) {
		tag[now] = 0;
		if (l == r) {
			sum[now] = DFS::dep[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(now << 1, l, mid);
		build(now << 1 | 1, mid + 1, r);
		sum[now] = sum[now << 1] + sum[now << 1 | 1];
	}
	void add(int now, int l, int r, int val) {
		if (l != r) tag[now] += val;
		sum[now] += val * (r - l + 1);
	}
	void pd(int now, int l, int mid, int r) {
		add(now << 1, l, mid, tag[now]);
		add(now << 1 | 1, mid + 1, r, tag[now]);
		tag[now] = 0;
	}
	void query(int now, int l, int r, int ll, int rr) {
		if (ll <= l && r <= rr) {
			ans += sum[now];
			return;
		}
		int mid = (l + r) >> 1;
		if (tag[now]) pd(now, l, mid, r);
		if (ll <= mid) query(now << 1, l, mid, ll, rr);
		if (rr > mid) query(now << 1 | 1, mid + 1, r, ll, rr);
	}
	void change(int now, int l, int r, int ll, int rr, int val) {
		if (ll <= l && r <= rr) {
			add(now, l, r, val);
			return;
		}
		int mid = (l + r) >> 1;
		if (tag[now]) pd(now, l, mid, r);
		if (ll <= mid) change(now << 1, l, mid, ll, rr, val);
		if (rr > mid) change(now << 1 | 1, mid + 1, r, ll, rr, val);
		sum[now] = sum[now << 1] + sum[now << 1 | 1];
	}
}
namespace LCT {
	int c[N][2];
	void Init(int n) {
		for (int i = 1; i <= n; ++i)
			c[i][0] = c[i][1] = fa[i] = 0;
	}
	bool isroot(int x) {
		return c[fa[x]][0] != x && c[fa[x]][1] != x;
	}
	void rotate(int x) {
		int y = fa[x], z = fa[y], a = c[y][1] == x, b = a ^ 1;
		if (!isroot(y)) c[z][1]==y] = x;
		fa[x] = z; fa[y] = x;
		if (c[x][b]) fa[b]] = y;
		c[y][a] = c[x][b]; c[x][b] = y;
	}
	void splay(int x) {
		int y;
		while (!isroot(x)) {
			y = fa[x];
			if (!isroot(y)) {
				if (c[fa[y]][0] == y ^ c[y][0] == x) rotate(x);
				else rotate(y);
			}
			rotate(x);
		}
	}
	int Mag(int x, int j) {
		while (c[x][j]) x = c[x][j];
		return x;
	}
	void access(int x) {
		int y = 0, z;
		while (x) {
			splay(x);
			if (c[x][1]) {
				z = Mag(c[x][1], 0);
				SGT::change(1, 1, n, DFS::tid[z], DFS::dfn[z], 1);
			}
			if (y) {
				z = Mag(y, 0);
				SGT::change(1, 1, n, DFS::tid[z], DFS::dfn[z], -1);
			}
			c[x][1] = y;
			y = x;
			x = fa[x];
		}
	}
}
namespace HSK {
	int x, y, m, T;
	int getint() {
		int r = 0, k = 1; char c = getchar();
		for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
		for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
		return r * k;
	}
	void work() {
		T = getint();
		while (T--) {
			n = getint();
			LCT::Init(n);
			DFS::Init(n);
			for (int i = 1; i < n; ++i) {
				x = getint() + 1;
				y = getint() + 1;
				DFS::ins(x, y);
			}
			DFS::dfs(1, 0, 0);
			SGT::build(1, 1, n);
			m = getint();
			while (m--) {
				scanf("%s", str);
				x = getint() + 1;
				if (str[0] == 'O') LCT::access(x);
				else {
					ans = 0;
					SGT::query(1, 1, n, DFS::tid[x], DFS::dfn[x]);
					printf("%lld\n", ans);
				}
			}
		}
	}
}
int main() {
	freopen("kongzhi.in", "r", stdin);
	freopen("kongzhi.out", "w", stdout);
	HSK::work();
	fclose(stdin);
	fclose(stdout);
	return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据