Luogu3979 遥远的国度

博主： tony102
发布时间：2020 年 12 月 02 日
2004 次浏览
暂无评论
1226字数
分类：题解

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

## Sol

换根树剖是个假的, 只要讨论新根在的位置就好了

分三种情况

第一种换的新根就是现在的根,那么该咋就咋(我也不知道为什么所有的题解都要讨论这种情况,但是我还是讨论了)

第二种就是换的新根和原来的根的lca就是新根,也就是说,原来的跟就在新根的子树中, 那么要操作的实际位置是新根的下面一个点

第三种就是新根和原来的根在以第一个根为根的树中分属不同的子树中,那么换根的操作实际上啥影响也没有.直接在新根的子树中查就可以了

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 1e5 + 5;
const int inf = 0x7f7f7f7f;

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

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

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

namespace ae86 {
	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 (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using ae86::read;

inline void addEdge(int u, int v) {
	edge[++ num].to = v, edge[num].nxt = head[u];
	head[u] = num;
}

inline 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;
	}
}

inline void dfs2(int u, int top) {
	dfn[u] = ++ ind, idx[ind] = 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);
	}
}

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

inline void pushUp(int p) {
	tree[p].minn = std::min(tree[lson(p)].minn, tree[rson(p)].minn);
}

inline void pushDown(int p) {
	if (tree[p].tag != inf) {
		tree[lson(p)].minn = tree[rson(p)].minn = tree[p].tag;
		tree[lson(p)].tag = tree[rson(p)].tag = tree[p].tag;
		tree[p].tag = inf;
	}
}

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

inline void modify(int p, int l, int r, int val) {
	if (l <= tree[p].l && tree[p].r <= r) {
		tree[p].minn = 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);
}

inline int queryMin(int p, int l, int r) {
	if (l <= tree[p].l && tree[p].r <= r) {
		return tree[p].minn;
	}
	pushDown(p);
	int mid = (tree[p].l + tree[p].r) >> 1, ans = inf;
	if (l <= mid) ans = std::min(ans, queryMin(lson(p), l, r));
	if (r > mid) ans = std::min(ans, queryMin(rson(p), l, r));
	return ans;
}

inline 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;
}

inline void modifyPath(int u, int v, int val) {
	while (bel[u] != bel[v]) {
		if (dep[bel[u]] < dep[bel[v]]) std::swap(u, v);
		modify(1, dfn[bel[u]], dfn[u], val);
		u = fa[bel[u]];
	}	
	if (dfn[u] > dfn[v]) std::swap(u, v);
	modify(1, dfn[u], dfn[v], val);
}

inline int queryPath(int u, int v) {
	int ans = inf;
	while (bel[u] != bel[v]) {
		if (dep[bel[u]] < dep[bel[v]]) std::swap(u, v);
		ans = std::min(ans, queryMin(1, dfn[bel[u]], dfn[u]));
		u = fa[bel[u]];
	}
	if (dfn[u] > dfn[v]) std::swap(u, v);
	ans = std::min(ans, queryMin(1, dfn[u], dfn[v]));
	return ans;
}

inline 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];
	}
	// if (dep[u] < dep[v]) std::swap(u, v);
	// return son[v];
	return dfn[u] > dfn[v] ? son[v] : son[u];
}

inline int ask(int rt) {
	if (rt == root) return queryMin(1, 1, n);
	int ff = lca(root, rt), ans = inf;
	if (rt == ff) {
		int u = find(rt, root);
		if (dfn[u] > 1) ans = std::min(queryMin(1, 1, dfn[u] - 1),ans);
		if (dfn[u] + siz[u] <= n) ans = std::min(queryMin(1, dfn[u] + siz[u], n), ans);
		return ans; 
	}
	else return queryMin(1, dfn[rt], dfn[rt] + siz[rt] - 1); 
}

signed main() {
	// freopen("code.in", "r", stdin);
	// freopen("code.out", "w", stdout);
	n = read(), m = read();
	for (int i = 1, u, v; i < n; ++ i) {
		u = read(), v = read();
		addEdge(u, v); addEdge(v, u);
	}
	for (int i = 1; i <= n; ++ i) w[i] = read();
	root = read();
	dfs1(root, 0); dfs2(root, root);
	build(1, 1, n);
	int opt, u, v, d;	
	while (m --) {
		opt = read();
		if (opt == 1) root = read();
		else if (opt == 2) {
			u = read(), v = read(), d = read();
			modifyPath(u, v, d);
		}
		else if (opt == 3) {
			u = read();
			printf("%lld\n", ask(u));
		}
	}
	return 0;
}
```

最后修改：2021 年 09 月 04 日

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

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

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

暴力膜托
暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托%%%
TosakaUCW
前排狂暴膜托！
菲兹克斯喵
竟然……又找到一个校友……而且初中和高中都是同一个学校……天哪...
暴力膜托
快给黄明珍开个方子吧，可怜孩子补太猛了
Yanws
牢师求更新

Luogu3979 遥远的国度

tony102 • 2020 年 12 月 02 日

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

## Sol

换根树剖是个假的, 只要讨论新根在的位置就好了

分三种情况

第一种换的新根就是现在的根,那么该咋就咋(我也不知道为什么所有的题解都要讨论这种情况,但是我还是讨论了)

第二种就是换的新根和原来的根的lca就是新根,也就是说,原来的跟就在新根的子树中, 那么要操作的实际位置是新根的下面一个点

第三种就是新根和原来的根在以第一个根为根的树中分属不同的子树中,那么换根的操作实际上啥影响也没有.直接在新根的子树中查就可以了

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 1e5 + 5;
const int inf = 0x7f7f7f7f;

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

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

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

inline void addEdge(int u, int v) {
	edge[++ num].to = v, edge[num].nxt = head[u];
	head[u] = num;
}

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

inline void pushUp(int p) {
	tree[p].minn = std::min(tree[lson(p)].minn, tree[rson(p)].minn);
}

inline void pushDown(int p) {
	if (tree[p].tag != inf) {
		tree[lson(p)].minn = tree[rson(p)].minn = tree[p].tag;
		tree[lson(p)].tag = tree[rson(p)].tag = tree[p].tag;
		tree[p].tag = inf;
	}
}

inline 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;
}

Luogu3979 遥远的国度

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

名人传

VP: AtCoder Beginner Contest 222(ABC222)

写在 CSP-S2021 前

机房标准化岚语发音对照

VP: AtCoder Beginner Contest 221(ABC221)

Annotation Free Semantic Segmentation with Vision Foundation Models

20210913 子段排序 (subarray)

ARC125E Snack

机房标准化岚语发音对照

CF1025D Recovering BST

Luogu3979 遥远的国度

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

Luogu3979 遥远的国度

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