周赛120 https://ac.nowcoder.com/acm/contest/123788
E.无穷无尽的树
- 分享一个较为轮椅的做法
HLD+线段树
题目每次求一个节点的子树中深度最深的节点个数，看到子树，可以想到dfs序，通过in数组与out数组将树上操作转换为线性数组操作。
从而可以做到O(1)时间找到这个子树（即在dfs序中的进入与离开该子树的下标），由于题目只让求个数，所以用与dfs序相对应的一个深度数组记录深度信息。
然后将这个记录了深度信息的数组进行区间查询，即从在dfs序中的进入该子树到离开该子树的这个区间内进行区间查询最大值的数量。由于要查询n个子树，因此根据数据范围，我们每次查询的时间复杂度不超过O（logn）,因此我们可以使用线段树进行处理区间查询。
现在就是查询的是数量，而不是最大深度是多少，我们用哥哥的板子的Info可以很简单的实现这个功能。
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using u32 = unsigned;
using d32 = double;
using d64 = long double;
using i64 = long long;
using u64 = unsigned long long;
using pll = pair<long long, long long>;
using pii = pair<int, int>;
#ifdef __SIZEOF_INT128__
using i128 = __int128;
#endif
//真正的solve在 543 行
//懒更新线段树板子在 122 行
//树链剖分板子在 426 行
//火车头
template <class T1, class T2>
istream &operator>>(istream &cin, pair<T1, T2> &a) { return cin >> a.first >> a.second; }
template <class T1>
istream &operator>>(istream &cin, vector<T1> &a)
{
for (auto &x : a)
cin >> x;
return cin;
}
template <class T1, class T2>
ostream &operator<<(ostream &cout, const pair<T1, T2> &a) { return cout << a.first << ' ' << a.second; }
template <class T1, class T2>
ostream &operator<<(ostream &cout, const vector<pair<T1, T2>> &a)
{
for (auto &x : a)
cout << x << '\n';
return cout;
}
template <class T1>
ostream &operator<<(ostream &cout, vector<T1> a)
{
int n = a.size();
if (!n)
return cout;
cout << a[0];
for (int i = 1; i < n; i++)
cout << ' ' << a[i];
return cout;
}
template <class T1>
ostream &operator<<(ostream &cout, const vector<vector<T1>> &a)
{
int n = a.size();
if (!n)
return cout;
cout << a[0];
for (int i = 1; i < n; i++)
cout << '\n'
<< a[i];
return cout;
}
template <typename T, typename Container, typename Compare>
ostream &operator<<(ostream &cout, priority_queue<T, Container, Compare> pq)
{
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
return cout;
}
template <typename T, typename Container>
ostream &operator<<(ostream &cout, queue<T, Container> q)
{
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
return cout;
}
template <typename T>
ostream &operator<<(ostream &cout, const deque<T> &dq)
{
for (const auto &elem : dq)
{
cout << elem << " ";
}
cout << endl;
return cout;
}
template <typename T, typename Container>
ostream &operator<<(ostream &cout, stack<T, Container> stk)
{
while (!stk.empty())
{
cout << stk.top() << " ";
stk.pop();
}
cout << endl;
return cout;
}
static mt19937 randomEngine(random_device{}());
static vector<i64> randInts(int n, i64 mi, i64 mx)
{
uniform_int_distribution<i64> dist(mi, mx);
vector<i64> result(n);
for (int i = 0; i < n; ++i)
{
result[i] = dist(randomEngine);
}
return result;
}
const int dx[8] = {0, 0, 1, -1, -1, -1, 1, 1};
const int dy[8] = {1, -1, 0, 0, -1, 1, -1, 1};
void mainInit()
{
}
//哥哥的懒更新线段树板子，其实这个题目只有区间查询操作，我懒得换普通线段树板子了
constexpr i64 inf = 1E18;
template <class Info, class Tag>
struct LazySegmentTree
{
int n;
vector<Info> info;
vector<Tag> tag;
LazySegmentTree() : n(0) {}
LazySegmentTree(int n_, Info v_ = Info())
{
init(n_, v_);
}
template <class T>
LazySegmentTree(std::vector<T> init_)
{
init(init_);
}
void init(int n_, Info v_ = Info())
{
init(std::vector(n_, v_));
}
template <class T>
void init(std::vector<T> init_)
{
n = init_.size();
info.assign(4 << std::__lg(n), Info());
tag.assign(4 << std::__lg(n), Tag());
std::function<void(int, int, int)> build = [&](int p, int l, int r)
{
if (r - l == 1)
{
info[p] = init_[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) // 聚合
{
info[p] = info[2 * p] + info[2 * p + 1];
}
void apply(int p, const Tag &v)
{
info[p].apply(v);
tag[p].apply(v);
}
void push(int p) // 分发
{
apply(2 * p, tag[p]);
apply(2 * p + 1, tag[p]);
tag[p] = Tag();
}
// 单点修改，把x位置改成v
void modify(int p, int l, int r, int x, const Info &v)
{
if (r - l == 1)
{
info[p] = v;
}
int m = (r + l) / 2;
push(p);
if (x < m)
{
modify(2 * p, l, m, x, v);
}
else
{
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v)
{
modify(1, 0, n, p, v);
}
// 区间查询
Info rangeQuery(int p, int l, int r, int x, int y)
{
if (l >= y || r <= x)
{
return Info();
}
if (l >= x && r <= y)
{
return info[p];
}
int m = (l + r) / 2;
push(p);
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
}
Info rangeQuery(int l, int r)
{
return rangeQuery(1, 0, n, l, r);
}
void rangeApply(int p, int l, int r, int x, int y, const Tag &v)
{
if (l >= y || r <= x)
{
return;
}
if (l >= x && r <= y)
{
apply(p, v);
return;
}
int m = (l + r) / 2;
push(p); // 因为懒更新，所以在处理子区间之前要分发下去
rangeApply(2 * p, l, m, x, y, v);
rangeApply(2 * p + 1, m, r, x, y, v);
pull(p);
}
void rangeApply(int l, int r, const Tag &v)
{
rangeApply(1, 0, n, l, r, v);
}
void half(int p, int l, int r)
{
if (info[p].act == 0)
{
return;
}
if ((info[p].min + 1) / 2 == (info[p].max + 1) / 2)
{
apply(p, {-(info[p].min + 1) / 2}); // 除以2向下取整
}
int m = (l + r) / 2;
push(p);
half(2 * p, l, m);
half(2 * p + 1, m, r);
pull(p);
}
void half()
{
half(1, 0, n);
}
template <class F>
int findFirst(int p, int l, int r, int x, int y, F &&pred)
{
if (l >= y || r <= x)
{
return -1;
}
if (l >= x && r <= y && !pred(info[p]))
{
return -1;
}
if (r - l == 1)
{
return l;
}
int m = (l + r) / 2;
push(p);
int res = findFirst(2 * p, l, m, x, y, pred);
if (res == -1)
{
res = findFirst(2 * p + 1, m, r, x, y, pred);
}
return res;
}
template <class F>
int findFirst(int l, int r, F &&pred)
{
return findFirst(1, 0, n, l, r, pred);
}
template <class F>
int findLast(int p, int l, int r, int x, int y, F &&pred)
{
if (l >= y || r <= x)
{
return -1;
}
if (l >= x && r <= y && !pred(info[p]))
{
return -1;
}
if (r - l == 1)
{
return l;
}
int m = (l + r) / 2;
push(p);
int res = findLast(2 * p + 1, m, r, x, y, pred);
if (res == -1)
{
res = findLast(2 * p, l, m, x, y, pred);
}
return res;
}
template <class F>
int findLast(int l, int r, F &&pred)
{
return findLast(1, 0, n, l, r, pred);
}
void maintainL(int p, int l, int r, int pre)
{
if (info[p].difl > 0 && info[p].maxlowl < pre)
{
return;
}
if (r - l == 1)
{
info[p].max = info[p].maxlowl;
info[p].maxl = info[p].maxr = l;
info[p].maxlowl = info[p].maxlowr = -inf;
return;
}
int m = (l + r) / 2;
push(p);
maintainL(2 * p, l, m, pre);
pre = std::max(pre, info[2 * p].max);
maintainL(2 * p + 1, m, r, pre);
pull(p);
}
void maintainL()
{
maintainL(1, 0, n, -1);
}
void maintainR(int p, int l, int r, int suf)
{
if (info[p].difr > 0 && info[p].maxlowr < suf)
{
return;
}
if (r - l == 1)
{
info[p].max = info[p].maxlowl;
info[p].maxl = info[p].maxr = l;
info[p].maxlowl = info[p].maxlowr = -inf;
return;
}
int m = (l + r) / 2;
push(p);
maintainR(2 * p + 1, m, r, suf);
suf = std::max(suf, info[2 * p + 1].max);
maintainR(2 * p, l, m, suf);
pull(p);
}
void maintainR()
{
maintainR(1, 0, n, -1);
}
};
struct Tag
{
void apply(Tag t) {}
};
//这里记录最大深度与最大深度的个数信息
struct Info
{
i64 max_dep = -inf;
i64 cnt = 0;
void apply(Tag t) {}
};
Info operator+(Info a, Info b)
{
Info c;
if (a.max_dep > b.max_dep)
{
c.max_dep = a.max_dep;
c.cnt = a.cnt;
}
else if (a.max_dep < b.max_dep)
{
c.max_dep = b.max_dep;
c.cnt = b.cnt;
}
else
{
c.max_dep = a.max_dep;
c.cnt = (a.max_dep == -inf) ? 0 : (a.cnt + b.cnt);
}
return c;
}
//哥哥的树链剖分板子
struct HLD
{
int n;
vector<int> siz, top, dep, parent, in, out, seq;
vector<vector<int>> adj;
int cur;
HLD() {}
HLD(int n)
{
init(n);
}
void init(int n)
{
this->n = n;
siz.resize(n);
top.resize(n);
dep.resize(n);
parent.resize(n);
in.resize(n);
out.resize(n);
seq.resize(n);
cur = 0;
adj.assign(n, {});
}
void addedge(int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
void work(int root = 0)
{
top[root] = root;
dep[root] = 0;
parent[root] = -1;
dfs1(root);
dfs2(root);
}
void dfs1(int u)
{
if (parent[u] != -1)
{
adj[u].erase(find(adj[u].begin(), adj[u].end(), parent[u]));
}
siz[u] = 1;
for (auto &v : adj[u])
{
parent[v] = u;
dep[v] = dep[u] + 1;
dfs1(v);
siz[u] += siz[v];
if (siz[v] > siz[adj[u][0]])
{
swap(v, adj[u][0]);
}
}
}
void dfs2(int u)
{
in[u] = cur;
cur++;
seq[in[u]] = u;
for (auto v : adj[u])
{
top[v] = (v == adj[u][0]) ? top[u] : v;
dfs2(v);
}
out[u] = cur;
}
int lca(int u, int v)
{
while (top[u] != top[v])
{
if (dep[top[u]] > dep[top[v]])
{
u = parent[top[u]];
}
else
{
v = parent[top[v]];
}
}
return dep[u] < dep[v] ? u : v;
}
int dist(int u, int v)
{
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
int jump(int u, int k)
{
if (dep[u] < k)
{
return -1;
}
int d = dep[u] - k;
while (dep[top[u]] > d)
{
u = parent[top[u]];
}
return seq[in[u] - dep[u] + d];
}
bool isAncester(int u, int v)
{
return in[u] <= in[v] && in[v] < out[u];
}
};
//轮椅做法
void solve()
{
int n;
cin >> n;
HLD hld(n);
for (int i = 0; i < n - 1; i++)
{
int u, v;
cin >> u >> v;
u--;
v--;
hld.addedge(u, v);
}
hld.work(0);
vector<bool> is_leaf(n, false);
for (int u = 0; u < n; u++)
{
if (hld.parent[u] != -1 && hld.siz[u] == 1)
{
is_leaf[u] = true;
}
}
vector<Info> init_info(n);
for (int pos = 0; pos < n; pos++)
{
int u = hld.seq[pos];
if (is_leaf[u])
{
init_info[pos] = Info{-inf, 0};
}
else
{
init_info[pos] = Info{(i64)hld.dep[u], 1};
}
}
LazySegmentTree<Info, Tag> seg(init_info);
vector<i64> ans(n);
for (int x = 0; x < n; x++)
{
Info res = seg.rangeQuery(hld.in[x], hld.out[x]);
ans[x] = (res.max_dep == -inf) ? 0 : res.cnt;
}
for (int i = 0; i < n; i++)
{
cout << ans[i] << " ";
}
cout << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
mainInit();
i64 t = 1;
while (t--)
{
solve();
}
return 0;
}
京公网安备 11010502036488号