Submission #53755

ソースコード

?
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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#include "bits/stdc++.h"
#define rep(i, n) for (i64 i = 0, i##_limit = (n); i < i##_limit; ++i)
using namespace std;
using i64 = int_fast64_t;
template<class T, class U>inline bool chmax(T &a, const U &b){return b>a && (a=b, true);}
template<class T, class U>inline bool chmin(T &a, const U &b){return b<a && (a=b, true);}
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
struct Edge { // {{{
int src, to;
int64_t cost = 0;
inline Edge(int src, int to, const int64_t &cost) noexcept :
src(src), to(to), cost(cost) {}
inline Edge(int to, const int64_t &cost) noexcept :
src(-1), to(to), cost(cost) {}
inline Edge() noexcept {}
bool operator< (const Edge &o) const noexcept { return cost < o.cost; }
bool operator> (const Edge &o) const noexcept { return o < *this; }
Edge& operator=(int to) noexcept {
this->to = to;
return *this;
}
operator int() const noexcept { return to; }
};
// }}}
using WeightedGraph = vector<vector<Edge>>;
using UnWeightedGraph = vector<vector<int>>;
class HeavyLightDecomposition { // {{{
public:
WeightedGraph G; // 重み付きグラフ
const int V; // ノード数
vector<int> parent; // 親
vector<int> treeSize; // 自分も含めた部分木のサイズ
vector<int> head; // HL分解後の自分が属するグループ(チェイン)の先頭ノード
vector<int> vid; // 根からDFSしたときにそのノードを訪れた順番
vector<int> nodeOfVid; // vidからノードを逆算する用
vector<int64_t> weightSum; // 根からのコストの総和
vector<int> depth; // 根からの深さ(経由するエッジの数)
HeavyLightDecomposition() = delete;
// 空の木を構築する。管理できるノードは [0, V) なので注意。
explicit HeavyLightDecomposition(int V) :
G(V), V(V),
parent(V, -1), treeSize(V), head(V),
vid(V), nodeOfVid(V),
weightSum(V, 0),
depth(V, 0) {}
// u-v間に無向辺を張る。重みは省略可
inline void addEdge(int u, int v, int64_t weight = 1) {
G[u].emplace_back(u, v, weight);
G[v].emplace_back(v, u, weight);
}
// HL分解、その他もろもろ前計算
void build(int root = 0) {
int timestamp = 0;
head[root] = root;
dfs_treeSize(root);
dfs_HLDecomp(root, timestamp);
}
// u,v の最小共通祖先を求める
int lca(int u, int v) const {
while(head[u] != head[v]) {
if (vid[u] > vid[v]) swap(u, v);
v = parent[head[v]];
}
return (vid[u] < vid[v]) ? u : v;
}
// 根に向かって v から k だけ登ったノードを求める
int climb(int v, int k) const {
while(1) {
const int h = head[v];
if (vid[v] - k >= vid[h]) return nodeOfVid[vid[v] - k];
k -= vid[v] - vid[h] + 1;
v = parent[h];
}
}
// u-v間のパスの重みの和を求める
int64_t pathWeight(int u, int v) const {
return weightSum[u] + weightSum[v] - (2 * weightSum[lca(u, v)]);
}
// u-v間のパスの「エッジの個数」を求める
int pathCountEdge(int u, int v) const {
return depth[u] + depth[v] - (2 * depth[lca(u, v)]) + 1;
}
private: // {{{
// treeSize[v], parent[v], depth[v], weightSum[v] を再帰によって計算
// v の子の中で最もheavyなやつを G[v] の先頭にもってくる
int dfs_treeSize(int v) {
treeSize[v] = 1;
if (!G[v].empty() && G[v].front().to == parent[v]) swap(G[v].front(), G[v].back());
for (auto &e : G[v]) {
if (e.to == parent[v]) continue;
parent[e.to] = v;
depth[e.to] = depth[v] + 1;
weightSum[e.to] = weightSum[v] + e.cost;
treeSize[v] += dfs_treeSize(e.to);
if (treeSize[e.to] > treeSize[G[v].front()]) swap(e, G[v].front());
}
return treeSize[v];
}
// G[v] の先頭に v の子中で最もheavyなノードがある前提でHL分解し、
// vid[v], nodeOfVid[v], head[v] を求める
void dfs_HLDecomp(int v, int ×tamp) {
vid[v] = timestamp;
nodeOfVid[timestamp] = v;
++timestamp;
for (const int to : G[v]) {
if (to == parent[v]) continue;
head[to] = (to == G[v].front() ? head[v] : to);
dfs_HLDecomp(to, timestamp);
}
} // }}}
}; // }}}
signed main()
{
ios::sync_with_stdio(false); cin.tie(nullptr);
int N, Q;
cin >> N >> Q;
HeavyLightDecomposition G(N+1);
rep(i, N - 1) {
int u, v, w;
cin >> u >> v >> w;
G.addEdge(u, v, w);
}
// 根のノードを1としてHL分解
G.build(1);
// a-b, a-c, b-c の3つのパスの中で重みが最大のものを探し、
// { パスの始点, パスの終点 } のペアを返す。
const auto maxWeightPath = [&G](int a, int b, int c) -> pair<int,int> {
const auto weightAB = G.pathWeight(a, b);
const auto weightAC = G.pathWeight(a, c);
const auto weightBC = G.pathWeight(b, c);
const auto maxv = max({ weightAB, weightAC, weightBC });
if (maxv == weightAB) return { a, b };
if (maxv == weightAC) return { a, c };
return { b, c };
};
// s からlcaに向かって登る距離を [low, high) で2分探索
// (パス[s-lca]上で、weight(s, p) < weight(t, p) を満たし、s からできるだけ離れたノードを探索)
// 探索途中のノードも解の候補に含めるので逐次 res を更新する
const auto binSearch = [&G](int s, int lca, int t) -> i64 {
i64 res = LINF;
int low = 0;
int high = G.pathCountEdge(s, lca) + 1;
while(high - low > 1) {
const int mid = (low + high) / 2;
const int p = G.climb(s, mid);
const auto weightSP = G.pathWeight(s, p);
const auto weightTP = G.pathWeight(t, p);
chmin(res, max(weightSP, weightTP));
if (weightSP < weightTP) {
low = mid;
} else {
high = mid;
}
}
const int p = G.climb(s, low);
chmin(res, max(G.pathWeight(s, p), G.pathWeight(t, p)));
return res;
};
const auto solve = [&](int a, int b, int c) -> i64 {
int s, t;
tie(s, t) = maxWeightPath(a, b, c);
const int lca = G.lca(s, t);
return min(binSearch(s, lca, t), binSearch(t, lca, s));
};
rep(i, Q) {
int a, b, c;
cin >> a >> b >> c;
cout << solve(a, b, c) << "\n";
}
return 0;
}

ステータス

項目 データ
問題 1024 - 待ち合わせ
ユーザー名 Arumakan_ei1727
投稿日時 2019-08-28 22:02:00
言語 C++14
状態 Accepted
得点 14
ソースコード長 7057 Byte
最大実行時間 188 ms
最大メモリ使用量 86988 KB

セット

セット 得点 Cases
1 ALL 14 / 14 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1.txt AC 42 ms 604 KB
1
in2.txt AC 22 ms 556 KB
1
in3.txt AC 19 ms 676 KB
1
in4.txt AC 24 ms 14728 KB
1
in5.txt AC 19 ms 47548 KB
1
in6.txt AC 20 ms 73820 KB
1
in7.txt AC 18 ms 74024 KB
1
in8.txt AC 19 ms 73976 KB
1
in9.txt AC 23 ms 73924 KB
1
in10.txt AC 32 ms 560 KB
1
in11.txt AC 21 ms 640 KB
1
in12.txt AC 29 ms 592 KB
1
in13.txt AC 24 ms 668 KB
1
in14.txt AC 36 ms 612 KB
1
in15.txt AC 23 ms 560 KB
1
in16.txt AC 25 ms 640 KB
1
in17.txt AC 15 ms 588 KB
1
in18.txt AC 55 ms 664 KB
1
in19.txt AC 19 ms 484 KB
1
in20.txt AC 19 ms 512 KB
1
in21.txt AC 22 ms 588 KB
1
in22.txt AC 30 ms 528 KB
1
in23.txt AC 21 ms 596 KB
1
in24.txt AC 22 ms 668 KB
1
in25.txt AC 20 ms 740 KB
1
in26.txt AC 41 ms 808 KB
1
in27.txt AC 22 ms 868 KB
1
in28.txt AC 24 ms 800 KB
1
in29.txt AC 24 ms 868 KB
1
in30.txt AC 22 ms 752 KB
1
in31.txt AC 19 ms 692 KB
1
in32.txt AC 33 ms 884 KB
1
in33.txt AC 21 ms 948 KB
1
in34.txt AC 19 ms 884 KB
1
in35.txt AC 18 ms 952 KB
1
in36.txt AC 139 ms 22780 KB
1
in37.txt AC 145 ms 17940 KB
1
in38.txt AC 144 ms 19800 KB
1
in39.txt AC 175 ms 25160 KB
1
in40.txt AC 147 ms 26968 KB
1
in41.txt AC 144 ms 30480 KB
1
in42.txt AC 98 ms 33544 KB
1
in43.txt AC 87 ms 35548 KB
1
in44.txt AC 92 ms 38448 KB
1
in45.txt AC 127 ms 43692 KB
1
in46.txt AC 142 ms 46780 KB
1
in47.txt AC 188 ms 49720 KB
1
in48.txt AC 149 ms 54296 KB
1
in49.txt AC 135 ms 57376 KB
1
in50.txt AC 130 ms 60812 KB
1
in51.txt AC 141 ms 65236 KB
1
in52.txt AC 147 ms 71728 KB
1
in53.txt AC 124 ms 76224 KB
1
in54.txt AC 136 ms 78908 KB
1
in55.txt AC 129 ms 83320 KB
1
in56.txt AC 124 ms 86988 KB
1