ICPC ShenYang 2022 G

zzyNorthPole
  2023-02-01 23:06:03 2023-02-01 23:06:03 Created   2023-05-03 20:11:45 2023-05-03 20:11:45 Updated      

题目描述

给出两棵树，个询问

解题思路

一看到两棵树，就想到将其中的一棵的贡献提交到另一棵上。

我们考虑一组的情况。在固定的情况下，我们将所有的的贡献绑定到的对应节点上。

此时我们需要查找的东西转化为从点出发寻找一条最长的新路径。

最长的新路径我们考虑直径。任意一点的最长新路径必定是从该点到直径的某一端点。

对于固定一个点的情况我们直接求直径并查询结果即可。对于移动点的情况我们需要做一些拓展。

在移动的过程中直径的端点可能会发生变化。如何动态的更新呢？

结论：设点集和点集的直径端点分别为、、、。那么并集 的点集直径是这四个点中距离最远的两个点。

我们用如上的结论可以动态的更新直径。

具体做法是使用线段树维护每个区间内点集的直径的端点。可以想象，当点在树上移动的时候，某个dfs序区间内的所有点的都会减去一个值，此外的所有点都会加上一个值。加上一个值对端点答案没有影响。但是减去可能会，因此我们对于减去的答案做更新。

当回溯的时候，对于区间内的部分我们只需要初始化为之前的答案即可，区间外的部分不需要操作。

我们可以使用欧拉序+st表做到对lca的查询，因此总的时间复杂度就是。

给出代码，写的太辛苦了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <cstdio>
#include <vector>
#define zzynp
using std::vector;
using std::swap;
using std::max;
typedef long long LL;
const int N = 1e5 + 5;
int lg[N << 1];
struct EDGE {
	int v, w;
};
struct GRAPH {
	vector <EDGE> g[N];
	void addedge(int u, int v, int w) {
		g[u].push_back((EDGE) {v, w});
		g[v].push_back((EDGE) {u, w});
	}
	int dfn[N], idfn[N], dfs_clock, dep[N], sz[N];
	int st[N << 1][21], ist[N], eu_cnt;
	LL path[N];
	void dfs(int x, int px) {
		dfn[x] = ++dfs_clock, idfn[dfs_clock] = x;
		dep[x] = dep[px] + 1, sz[x] = 1;
		st[++eu_cnt][0] = x, ist[x] = eu_cnt;
		for (auto e : g[x]) {
			int v = e.v, w = e.w;
			if (v == px) continue;
			path[v] = path[x] + w;
			dfs(v, x);
			st[++eu_cnt][0] = x;
			sz[x] += sz[v];
		}
	}
	void build_st(int n) {
		int sz = n * 2 - 1;
		for (int step = 1; (1 << step) <= sz; ++step) {
			for (int i = 1; i + (1 << step) - 1 <= sz; ++i) {
				int tmpx = st[i][step - 1], tmpy = st[i + (1 << (step - 1))][step - 1];
				st[i][step] = dep[tmpx] < dep[tmpy] ? tmpx : tmpy;
			}
		}
	}
	int lca(int x, int y) {
		if (ist[x] > ist[y]) swap(x, y);
		int tmp = lg[ist[y] - ist[x] + 1];
		int tmpx = st[ist[x]][tmp], tmpy = st[ist[y] - (1 << tmp) + 1][tmp];
		return dep[tmpx] < dep[tmpy] ? tmpx : tmpy;
	}
	LL dist(int x, int y) {
		return path[x] + path[y] - path[lca(x, y)] * 2;
	}
} g1, g2;
struct POINT {
	int l, r;
};
LL qry_dist(int x, int y, int p) {
	return g1.dist(p, x) + g1.dist(p, y) + g2.dist(x, y);
}
POINT merge(POINT x, POINT y, int p) {
	int tmp[4] = {x.l, x.r, y.l, y.r};
	int tmpx = -1, tmpy = -1;
	for (int i = 0; i < 4; ++i) {
		if (tmp[i] != -1) {
			if (tmpx == -1) tmpx = tmp[i];
			else if (tmpy == -1) tmpy = tmp[i];
		}
	}
	LL len = 0LL;
	for (int i = 0; i < 4; ++i) {
		for (int j = i + 1; j < 4; ++j) {
			if (tmp[i] == -1 || tmp[j] == -1) continue;
			if (qry_dist(tmp[i], tmp[j], p) > len) {
				len = qry_dist(tmp[i], tmp[j], p);
				tmpx = tmp[i], tmpy = tmp[j];
			}
		}
	}
	return (POINT) {tmpx, tmpy};
}
struct SMT {
	#define lch(o) (o << 1)
	#define rch(o) (o << 1 | 1)
	POINT dmt[N << 2];
	void build(int o, int l, int r) {
		if (l == r) {
			dmt[o] = (POINT) {g1.idfn[l], -1};
			return;
		}
		int mid = (l + r) >> 1;
		build(lch(o), l, mid), build(rch(o), mid + 1, r);
		dmt[o] = merge(dmt[lch(o)], dmt[rch(o)], 1);
	}
	void chg(int o, int l, int r, int ls, int rs, int p) {
		if (ls <= l && r <= rs) return;
		int mid = (l + r) >> 1;
		if (ls <= mid) chg(lch(o), l, mid, ls, rs, p);
		if (rs > mid) chg(rch(o), mid + 1, r, ls, rs, p);
		dmt[o] = merge(dmt[lch(o)], dmt[rch(o)], p);
	}
	POINT qry(int o, int l, int r, int ls, int rs, int p) {
		if (ls <= l && r <= rs) return dmt[o];
		int mid = (l + r) >> 1;
		POINT tmpl = (POINT) {-1, -1}, tmpr = (POINT) {-1, -1};
		if (ls <= mid) tmpl = qry(lch(o), l, mid, ls, rs, p);
		if (rs > mid) tmpr = qry(rch(o), mid + 1, r, ls, rs, p);
		return merge(tmpl, tmpr, p);
	}
	#undef lch
	#undef rch
} smt;
struct QUERY {
	int r, id;
};
vector <QUERY> Q[N];
LL ans[N * 5];
void dfs_ans(int x, int px, int n) {
	smt.chg(1, 1, n, g1.dfn[x], g1.dfn[x] + g1.sz[x] - 1, x);
	POINT tmp_ans = smt.qry(1, 1, n, 1, n, x);
	for (auto tmp : Q[x]) {
		int tmpx = tmp.r;
		LL tmp1 = tmp_ans.l > 0 ? g1.dist(tmp_ans.l, x) + g2.dist(tmp_ans.l, tmpx) : 0;
		LL tmp2 = tmp_ans.r > 0 ? g1.dist(tmp_ans.r, x) + g2.dist(tmp_ans.r, tmpx) : 0;
		ans[tmp.id] = max(tmp1, tmp2);
	}
	for (auto e : g1.g[x]) {
		int v = e.v;
		if (v == px) continue;
		dfs_ans(v, x, n);
	}
	if (px) smt.chg(1, 1, n, g1.dfn[x], g1.dfn[x] + g1.sz[x] - 1, px);
}
int main() {
	int n, T;
	scanf("%d%d", &n, &T);
	g1.dfs_clock = g2.dfs_clock = 0;
	g1.eu_cnt = g2.eu_cnt = 0;
	for (int i = 1; i < n; ++i) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		g1.addedge(x, y, z);
	}
	for (int i = 1; i < n; ++i) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		g2.addedge(x, y, z);
	}
	for (int i = 2; i <= n * 2 - 1; ++i) lg[i] = lg[i >> 1] + 1;
	g1.dfs(1, 0), g2.dfs(1, 0);
	g1.build_st(n), g2.build_st(n);
	smt.build(1, 1, n);
	for (int i = 1; i <= T; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		Q[x].push_back((QUERY) {y, i});
	}
	dfs_ans(1, 0, n);
	for (int i = 1; i <= T; ++i) printf("%lld\n", ans[i]);
	return 0;
}
  • Title: ICPC ShenYang 2022 G
  • Author: zzyNorthPole
  • Created at : 2023-02-01 23:06:03
  • Updated at : 2023-05-03 20:11:45
  • Link: https://zzynorthpole.github.io/2023/02/01/ICPC-shenyang-2022-G/
  • License: This work is licensed under CC BY-NC-SA 4.0.
On this page
ICPC ShenYang 2022 G
  1. 题目描述
  2. 解题思路