CF916E Jamie and Tree

博主： tony102
发布时间：2021 年 03 月 31 日
1032 次浏览
暂无评论
705字数
分类：题解

[Link](https://www.luogu.com.cn/problem/CF916E)

## Sol

u1s1 这道题没有修改与 LCA 有关的的话，跟 [Luogu3979 遥远的国度](https://www.luogu.com.cn/problem/P3979) 这道题挺像的。众所周知的事情是，换根树剖其实完全不需要“换根”操作，仅仅需要讨论新的根与当前根的关系。

当 $u$ 和 $v$ 在以新根 $root$ 为根的 LCA 为：$LCA(u, root)$, $LCA(v, root)$ 和 $LCA(u, v)$ 中深度最大的一个。根据 $root$ 是否在原来 $u$ 的子树内，我们可以轻易提取出以 $root$ 为根时 $u$ 的子树对应的区间。然后修改对应区间即可。

具体的实现推荐使用树剖，不树剖用倍增也是可以的，但是常数巨大，不开 O2 很难卡过去。

## Code

代码略长，但是很好理解
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 3e5 + 5;

int n, q, root, tim, num;
int head[SIZE], dfn[SIZE], bel[SIZE], idx[SIZE], w[SIZE], fa[SIZE], son[SIZE], siz[SIZE], dep[SIZE];

struct node {
	int to, nxt;
} edge[SIZE << 1];

struct seg {
	int l, r, val, tag;
} tree[SIZE << 2];

struct query {
	int opt, u, v, x;
} que[SIZE];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

#define lson(p) (p << 1)
#define rson(p) (p << 1 | 1)

void addEdge(int u, int v) {
	edge[++ num] = (node) {v, head[u]}, head[u] = num;
}

void dfs1(int u, int ff) {
	siz[u] = 1;
	for (int i = head[u], v; i; i = edge[i].nxt) {
		v = edge[i].to;
		if (v == ff) continue;
		fa[v] = u, dep[v] = dep[u] + 1;
		dfs1(v, u);
		siz[u] += siz[v];
		if (siz[son[u]] < siz[v]) son[u] = v;
	}
}

void dfs2(int u, int top) {
	dfn[u] = ++ tim, idx[tim] = u, bel[u] = top;
	if (son[u]) dfs2(son[u], top);
	for (int i = head[u], v; i; i = edge[i].nxt) {
		v = edge[i].to;
		if (v == son[u] || v == fa[u]) continue;
		dfs2(v, v);
	}
}

int lca(int u, int v) {
	while (bel[u] != bel[v]) {
		if (dep[bel[u]] < dep[bel[v]]) std::swap(u, v);
		u = fa[bel[u]];
	}
	return dfn[u] > dfn[v] ? v : u;
}

void pushUp(int p) {
	tree[p].val = tree[lson(p)].val + tree[rson(p)].val;
}

void pushDown(int p) {
	if (tree[p].tag) {
		int len1 = tree[lson(p)].r - tree[lson(p)].l + 1, len2 = tree[rson(p)].r - tree[rson(p)].l + 1;
		tree[lson(p)].val += len1 * tree[p].tag, tree[rson(p)].val += len2 * tree[p].tag;
		tree[lson(p)].tag += tree[p].tag, tree[rson(p)].tag += tree[p].tag;
		tree[p].tag = 0;
	}
}

void build(int p, int l, int r) {
	tree[p].l = l, tree[p].r = r;
	if (l == r) { tree[p].val = w[idx[l]]; return; }
	int mid = (l + r) >> 1;
	build(lson(p), l, mid), build(rson(p), mid + 1, r);
	pushUp(p);
}

void modify(int p, int l, int r, int val) {
	if (l <= tree[p].l && tree[p].r <= r) {
		int len = tree[p].r - tree[p].l + 1;
		tree[p].val += len * val, tree[p].tag += val;
		return;
	}
	pushDown(p);
	int mid = (tree[p].l + tree[p].r) >> 1;
	if (l <= mid) modify(lson(p), l, r, val);
	if (r > mid) modify(rson(p), l, r, val);
	pushUp(p);
}

int query(int p, int l, int r) {
	if (l <= tree[p].l && tree[p].r <= r) return tree[p].val;
	pushDown(p);
	int mid = (tree[p].l + tree[p].r) >> 1, ans = 0;
	if (l <= mid) ans += query(lson(p), l, r);
	if (r > mid) ans += query(rson(p), l, r);
	return ans;
}

int find(int u, int v) {
	while (bel[u] != bel[v]) {
		if (dep[bel[u]] < dep[bel[v]]) std::swap(u, v);
		if (fa[bel[u]] != v) u = fa[bel[u]];
		else return bel[u];
	}
	return dfn[u] > dfn[v] ? son[v] : son[u];
}

int ask(int u) {
	if (u == root) return query(1, 1, n);
	else if (dfn[root] < dfn[u] || dfn[root] > dfn[u] + siz[u] - 1) 
		return query(1, dfn[u], dfn[u] + siz[u] - 1);
	else {
		int t = find(root, u);
		return query(1, 1, n) - query(1, dfn[t], dfn[t] + siz[t] - 1);
	}
}

namespace subtask1 {
	void main() {
		for (int i = 1; i <= q; ++ i) {
			if (que[i].opt == 2) {
				int g = lca(que[i].u, que[i].v);
				modify(1, dfn[g], dfn[g] + siz[g] - 1, que[i].x);
			}
			if (que[i].opt == 3) 
				printf("%lld\n", query(1, dfn[que[i].x], dfn[que[i].x] + siz[que[i].x] - 1));
		}	
	}
}

namespace subtask2 {
	void main() {
		for (int i = 1; i <= q; ++ i) {
			if (que[i].opt == 1) root = que[i].x;
			if (que[i].opt == 3) printf("%lld\n", ask(que[i].x));
		}	
	}
}

namespace subtask3 {
	void main() {
		for (int i = 1; i <= q; ++ i) {
			if (que[i].opt == 1) root = que[i].x;
			if (que[i].opt == 2) {
				int g = que[i].u;
				modify(1, dfn[g], dfn[g] + siz[g] - 1, que[i].x);
			}
			if (que[i].opt == 3) printf("%lld\n", ask(que[i].x));
		}	
	}
}

namespace subtask4 {
	int isSub(int u, int v) { return (dfn[u] >= dfn[v] && dfn[u] <= dfn[v] + siz[v] - 1); }

void main() {
		for (int i = 1; i <= q; ++ i) {
			if (que[i].opt == 1) root = que[i].x;
			if (que[i].opt == 2) {
				int x = que[i].u, y = que[i].v, g = 0, res1 = isSub(x, root), res2 = isSub(y, root);
				if (res1 && res2) g = lca(x, y);
				else if ((res1 && !res2) || (res2 && !res1)) g = root;
				else {
					int t1 = lca(x, y), t2 = lca(x, root), t3 = lca(y, root);
					if (t1 == t2) g = t3; else if (t1 == t3) g = t2; else g = t1;
				}
				if (root == g) modify(1, 1, n, que[i].x);
				else if (dfn[root] < dfn[g] || dfn[root] > dfn[g] + siz[g] - 1)
					modify(1, dfn[g], dfn[g] + siz[g] - 1, que[i].x);
				else {
					int t = find(root, g);
					modify(1, 1, n, que[i].x); modify(1, dfn[t], dfn[t] + siz[t] - 1, -que[i].x);
				}
			}
			if (que[i].opt == 3) printf("%lld\n", ask(que[i].x));
		}
	}
}

signed main() {
	// freopen("tree.in", "r", stdin);
	// freopen("tree.out", "w", stdout);
	n = read(), q = read();
	for (int i = 1; i <= n; ++ i) w[i] = read();
	for (int i = 1, u, v; i < n; ++ i) {
		u = read(), v = read();
		addEdge(u, v); addEdge(v, u);
	}
	root = 1, dep[root] = 1;
	dfs1(root, 0), dfs2(root, root);
	build(1, 1, n);
	int cnt1 = 0, cnt2 = 0, cnt3 = 0, flag = 1;
	for (int i = 1; i <= q; ++ i) {
		que[i].opt = read();
		if (que[i].opt == 1) que[i].x = read(), ++ cnt1;
		if (que[i].opt == 2)
			que[i].u = read(), que[i].v = read(), que[i].x = read(), ++ cnt2, flag &= (que[i].u == que[i].v);
		if (que[i].opt == 3) que[i].x = read(), ++ cnt3;
	}
	subtask4::main();
	return 0;
}
```

最后修改：2021 年 08 月 20 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

CF916E Jamie and Tree

tony102 • 2021 年 03 月 31 日

[Link](https://www.luogu.com.cn/problem/CF916E)

## Sol

具体的实现推荐使用树剖，不树剖用倍增也是可以的，但是常数巨大，不开 O2 很难卡过去。

## Code

代码略长，但是很好理解
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 3e5 + 5;

int n, q, root, tim, num;
int head[SIZE], dfn[SIZE], bel[SIZE], idx[SIZE], w[SIZE], fa[SIZE], son[SIZE], siz[SIZE], dep[SIZE];

struct node {
	int to, nxt;
} edge[SIZE << 1];

struct seg {
	int l, r, val, tag;
} tree[SIZE << 2];

struct query {
	int opt, u, v, x;
} que[SIZE];

#define lson(p) (p << 1)
#define rson(p) (p << 1 | 1)

void addEdge(int u, int v) {
	edge[++ num] = (node) {v, head[u]}, head[u] = num;
}

int lca(int u, int v) {
	while (bel[u] != bel[v]) {
		if (dep[bel[u]] < dep[bel[v]]) std::swap(u, v);
		u = fa[bel[u]];
	}
	return dfn[u] > dfn[v] ? v : u;
}

void pushUp(int p) {
	tree[p].val = tree[lson(p)].val + tree[rson(p)].val;
}

namespace subtask2 {
	void main() {
		for (int i = 1; i <= q; ++ i) {
			if (que[i].opt == 1) root = que[i].x;
			if (que[i].opt == 3) printf("%lld\n", ask(que[i].x));
		}	
	}
}

namespace subtask4 {
	int isSub(int u, int v) { return (dfn[u] >= dfn[v] && dfn[u] <= dfn[v] + siz[v] - 1); }

CF916E Jamie and Tree

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

名人传

VP: AtCoder Beginner Contest 222(ABC222)

写在 CSP-S2021 前

机房标准化岚语发音对照

VP: AtCoder Beginner Contest 221(ABC221)

VP: AtCoder Beginner Contest 227 (ABC227)

AT2142 [ARC062E] AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer

20210915 二进制式 (binary)

点和向量的旋转

Luogu6620 [省选联考 2020 A 卷] 组合数问题

CF916E Jamie and Tree

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

CF916E Jamie and Tree

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款