Luogu3979 遥远的国度

博主： tony102
发布时间：2020 年 12 月 02 日
1439 次浏览
暂无评论
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技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

看透一切的人士
催更名人传
看透一切的人士
催更
tham
催更！！！！
wyzwyz
建议把从“小有名气的贫僧”之后的全删了，包括我这句，前面都是一...
潜心学习的打工人
催更

多项式全家桶
评论数： 0
Min_25 筛
评论数： 0
VP: AtCoder Beginner Contest 220(ABC220)
评论数： 0
20211108 游戏 (game)
评论数： 0
ARC124B XOR Matching 2
评论数： 0

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)

多项式全家桶

Min_25 筛

VP: AtCoder Beginner Contest 220(ABC220)

20211108 游戏 (game)

ARC124B XOR Matching 2

Luogu3979 遥远的国度

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

Luogu3979 遥远的国度

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