結果
| 問題 | No.1718 Random Squirrel |
| ユーザー |
👑  emthrm
|
| 提出日時 | 2021-10-23 00:18:46 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 220 ms / 2,000 ms |
| コード長 | 10,346 bytes |
| コンパイル時間 | 3,178 ms |
| コンパイル使用メモリ | 230,992 KB |
| 最終ジャッジ日時 | 2025-01-25 04:40:25 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 31 |
ソースコード
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr double EPS = 1e-8;
constexpr int MOD = 1000000007;
// constexpr int MOD = 998244353;
constexpr int DY[]{1, 0, -1, 0}, DX[]{0, -1, 0, 1};
constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1}, DX8[]{0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
IOSetup() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
std::cout << fixed << setprecision(20);
}
} iosetup;
struct EulerTour {
std::vector<int> tour, left, right, down, up, depth;
EulerTour(const std::vector<std::vector<int>> &graph, int root = 0) : graph(graph) {
int n = graph.size();
left.resize(n);
right.resize(n);
down.assign(n, -1);
up.assign(n, (n - 1) << 1);
int idx = 0;
dfs(-1, root, 0, idx);
}
template <typename Fn>
void v_update(int ver, Fn f) const { f(left[ver], right[ver] + 1); }
template <typename T, typename Fn>
T v_query(int ver, Fn f) const { return f(left[ver], right[ver] + 1); }
template <typename T, typename Fn>
T e_query(int u, int v, Fn f) const { return f(down[u] + 1, down[v] + 1); }
template <typename Fn>
void subtree_e_update(int ver, Fn f) const { f(down[ver] + 1, up[ver]); }
template <typename T, typename Fn>
T subtree_e_query(int ver, Fn f) const { return f(down[ver] + 1, up[ver]); }
private:
const std::vector<std::vector<int>> graph;
void dfs(int par, int ver, int now_depth, int &idx) {
left[ver] = tour.size();
tour.emplace_back(ver);
depth.emplace_back(now_depth);
for (int e : graph[ver]) {
if (e != par) {
down[e] = idx++;
dfs(ver, e, now_depth + 1, idx);
tour.emplace_back(ver);
depth.emplace_back(now_depth);
up[e] = idx++;
}
}
right[ver] = tour.size() - 1;
}
};
struct LowestCommonAncestorByDoubling {
std::vector<int> depth, dist;
LowestCommonAncestorByDoubling(const std::vector<std::vector<int>> &graph) : graph(graph) {
n = graph.size();
depth.resize(n);
dist.resize(n);
while ((1 << table_h) <= n) ++table_h;
parent.resize(table_h, std::vector<int>(n));
}
void build(int root = 0) {
is_built = true;
dfs(-1, root, 0, 0);
for (int i = 0; i + 1 < table_h; ++i) for (int ver = 0; ver < n; ++ver) {
parent[i + 1][ver] = parent[i][ver] == -1 ? -1 : parent[i][parent[i][ver]];
}
}
int query(int u, int v) const {
assert(is_built);
if (depth[u] > depth[v]) std::swap(u, v);
for (int i = 0; i < table_h; ++i) {
if ((depth[v] - depth[u]) >> i & 1) v = parent[i][v];
}
if (u == v) return u;
for (int i = table_h - 1; i >= 0; --i) {
if (parent[i][u] != parent[i][v]) {
u = parent[i][u];
v = parent[i][v];
}
}
return parent[0][u];
}
int distance(int u, int v) const {
assert(is_built);
return dist[u] + dist[v] - dist[query(u, v)] * 2;
}
private:
bool is_built = false;
int n, table_h = 1;
std::vector<std::vector<int>> graph, parent;
void dfs(int par, int ver, int now_depth, int now_dist) {
depth[ver] = now_depth;
dist[ver] = now_dist;
parent[0][ver] = par;
for (int e : graph[ver]) {
if (e != par) dfs(ver, e, now_depth + 1, now_dist + 1);
}
}
};
struct HeavyLightDecomposition {
std::vector<int> parent, subtree, id, inv, head;
HeavyLightDecomposition(const std::vector<std::vector<int>> &graph, int root = 0) : graph(graph) {
int n = graph.size();
parent.assign(n, -1);
subtree.assign(n, 1);
id.resize(n);
inv.resize(n);
head.resize(n);
dfs1(root);
head[root] = root;
int now_id = 0;
dfs2(root, now_id);
}
template <typename Fn>
void v_update(int u, int v, Fn f) const {
while (true) {
if (id[u] > id[v]) std::swap(u, v);
f(std::max(id[head[v]], id[u]), id[v] + 1);
if (head[u] == head[v]) return;
v = parent[head[v]];
}
}
template <typename T, typename F, typename G>
T v_query(int u, int v, F f, G g, const T ID) const {
T left = ID, right = ID;
while (true) {
if (id[u] > id[v]) {
std::swap(u, v);
std::swap(left, right);
}
left = g(left, f(std::max(id[head[v]], id[u]), id[v] + 1));
if (head[u] == head[v]) break;
v = parent[head[v]];
}
return g(left, right);
}
template <typename Fn>
void subtree_v_update(int ver, Fn f) const { f(id[ver], id[ver] + subtree[ver]); }
template <typename T, typename Fn>
T subtree_v_query(int ver, Fn f) const { return f(id[ver], id[ver] + subtree[ver]); }
template <typename Fn>
void e_update(int u, int v, Fn f) const {
while (true) {
if (id[u] > id[v]) std::swap(u, v);
if (head[u] == head[v]) {
f(id[u], id[v]);
break;
} else {
f(id[head[v]] - 1, id[v]);
v = parent[head[v]];
}
}
}
template <typename T, typename F, typename G>
T e_query(int u, int v, F f, G g, const T ID) const {
T left = ID, right = ID;
while (true) {
if (id[u] > id[v]) {
std::swap(u, v);
std::swap(left, right);
}
if (head[u] == head[v]) {
left = g(left, f(id[u], id[v]));
break;
} else {
left = g(left, f(id[head[v]] - 1, id[v]));
v = parent[head[v]];
}
}
return g(left, right);
}
template <typename Fn>
void subtree_e_update(int ver, Fn f) const { f(id[ver], id[ver] + subtree[ver] - 1); }
template <typename T, typename Fn>
T subtree_e_query(int ver, Fn f) const { return f(id[ver], id[ver] + subtree[ver] - 1); }
int lowest_common_ancestor(int u, int v) const {
while (true) {
if (id[u] > id[v]) std::swap(u, v);
if (head[u] == head[v]) return u;
v = parent[head[v]];
}
}
private:
std::vector<std::vector<int>> graph;
void dfs1(int ver) {
for (int &e : graph[ver]) {
if (e != parent[ver]) {
parent[e] = ver;
dfs1(e);
subtree[ver] += subtree[e];
if (subtree[e] > subtree[graph[ver].front()]) std::swap(e, graph[ver].front());
}
}
}
void dfs2(int ver, int &now_id) {
id[ver] = now_id++;
inv[id[ver]] = ver;
for (int e : graph[ver]) {
if (e != parent[ver]) {
head[e] = (e == graph[ver].front() ? head[ver] : e);
dfs2(e, now_id);
}
}
}
};
template <typename Abelian>
struct FenwickTreeSupportingRangeAddQuery {
FenwickTreeSupportingRangeAddQuery(int n_, const Abelian ID = 0) : n(n_), ID(ID) {
++n;
dat_const.assign(n, ID);
dat_linear.assign(n, ID);
}
void add(int left, int right, Abelian val) {
if (right < ++left) return;
for (int i = left; i < n; i += i & -i) {
dat_const[i] -= val * (left - 1);
dat_linear[i] += val;
}
for (int i = right + 1; i < n; i += i & -i) {
dat_const[i] += val * right;
dat_linear[i] -= val;
}
}
Abelian sum(int idx) const {
Abelian res = ID;
for (int i = idx; i > 0; i -= i & -i) res += dat_linear[i];
res *= idx;
for (int i = idx; i > 0; i -= i & -i) res += dat_const[i];
return res;
}
Abelian sum(int left, int right) const {
return left < right ? sum(right) - sum(left) : ID;
}
Abelian operator[](const int idx) const { return sum(idx, idx + 1); }
private:
int n;
const Abelian ID;
std::vector<Abelian> dat_const, dat_linear;
};
int main() {
int n, k; cin >> n >> k;
vector<vector<int>> graph(n);
REP(_, n - 1) {
int u, v; cin >> u >> v; --u; --v;
graph[u].emplace_back(v);
graph[v].emplace_back(u);
}
vector<int> d(k); REP(i, k) cin >> d[i], --d[i];
EulerTour euler_tour(graph, d.front());
sort(ALL(d), [&](int a, int b) -> bool { return euler_tour.left[a] < euler_tour.left[b]; });
// REP(i, k) cerr << d[i] << " \n"[i + 1 == k];
LowestCommonAncestorByDoubling lca(graph);
lca.build(d.front());
ll steiner = 0;
REP(i, k) steiner += lca.distance(d[i], d[(i + 1) % k]);
// cerr << steiner << '\n';
HeavyLightDecomposition hld(graph, d.front());
FenwickTreeSupportingRangeAddQuery<ll> bit(n);
REP(i, k) hld.v_update(d[i], d[(i + 1) % k], [&](int u, int v) -> void { bit.add(u, v, 1); });
vector<int> dist(n, -1), from(n, -1);
queue<int> que;
REP(i, n) {
if (bit[hld.id[i]] > 0) {
dist[i] = 0;
from[i] = i;
que.emplace(i);
}
}
while (!que.empty()) {
int ver = que.front(); que.pop();
for (int e : graph[ver]) {
if (dist[e] == -1) {
dist[e] = dist[ver] + 1;
from[e] = from[ver];
que.emplace(e);
}
}
}
// REP(i, n) cerr << dist[i] << " \n"[i + 1 == n];
vector<int> has_acorn(n, false);
REP(i, k) has_acorn[d[i]] = true;
vector<vector<pair<int, int>>> child(n);
auto f = [&](auto&& f, int par, int ver) -> void {
for (int e : graph[ver]) {
if (e == par) continue;
f(f, ver, e);
if (!child[e].empty()) {
child[ver].emplace_back(child[e].front().first + 1, e);
} else if (has_acorn[e]) {
child[ver].emplace_back(1, e);
}
}
sort(ALL(child[ver]), greater{});
};
f(f, -1, d.front());
auto g = [&](auto&& g, int par, int ver, int pd) -> void {
if (par != -1) {
child[ver].emplace_back(pd, par);
sort(ALL(child[ver]), greater{});
}
for (int e : graph[ver]) {
if (e == par) continue;
if (child[ver].empty()) {
assert(has_acorn[ver]);
g(g, ver, e, 1);
} else if (child[ver].front().second == e) {
if (child[ver].size() == 1) {
assert(has_acorn[ver]);
g(g, ver, e, 1);
} else {
g(g, ver, e, child[ver][1].first + 1);
}
} else {
g(g, ver, e, child[ver].front().first + 1);
}
}
};
g(g, -1, d.front(), 0);
REP(i, n) cout << steiner + dist[i] - (child[from[i]].empty() ? 0 : child[from[i]].front().first) << '\n';
return 0;
}