# 树上启发式合并

600E - Lomsat gelral

```#include <bits/stdc++.h>
#define ll long long

const int N = 1e5 + 7;

int n, cc[N], col[N], son[N], sz[N], skip[N];
ll ans[N];
std::vector<int> G[N];

void dfs1(int u, int fa = 0) {
sz[u] = 1;
for (auto v: G[u]) {
if (v == fa) continue;
dfs1(v, u);
sz[u] += sz[v];
if (sz[v] > sz[son[u]]) son[u] = v;
}
}

ll sum;
int cx;

void edt(int u, int fa, int k) {
cc[col[u]] += k;
if (k > 0 && cc[col[u]] >= cx) {
if (cc[col[u]] > cx)
sum = 0, cx = cc[col[u]];
sum += col[u];
}
for (auto v: G[u])
if (v != fa && !skip[v])
edt(v, u, k);
}

void dfs(int u, int fa = 0, bool kep = 0) {
for (auto v: G[u])
if (v != fa && v != son[u])
dfs(v, u);
if (son[u])
dfs(son[u], u, 1), skip[son[u]] = 1;
edt(u, fa, 1);
ans[u] = sum;
if (son[u])
skip[son[u]] = 0;
if (!kep)
edt(u, fa, -1), cx = sum = 0;
}

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", col + i);
for (int i = 1, u, v; i < n; i++) {
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs1(1);
dfs(1);
for (int i = 1; i <= n; i++)
printf("%lld%c", ans[i], " \n"[i == n]);
return 0;
}```
View Code

570D - Tree Requests

```#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second

const int N =  5e5 + 7;
std::vector<int> G[N];
std::vector<std::pii> que[N];
int cnt[N], n, m, dep[N], sz[N], son[N];
char s[N];
bool ans[N], skip[N];

void dfs1(int u, int d) {
dep[u] = d;
sz[u] = 1;
for (auto v: G[u]) {
dfs1(v, d + 1);
sz[u] += sz[v];
if (sz[v] > sz[son[u]]) son[u] = v;
}
}

void edt(int u) {
cnt[dep[u]] ^= (1 << (s[u] - ‘a‘));
for (auto v: G[u])
if (!skip[v]) edt(v);
}

bool check(int d) {
int res = 0;
for (int i = 0; i < 26; i++)
if (cnt[d] >> i & 1)
res++;
return res <= 1;
}

void dfs(int u, int keep = 0) {
for (auto v: G[u])
if (v != son[u]) dfs(v, 0);
if (son[u])
dfs(son[u], 1), skip[son[u]] = 1;
edt(u);
for (auto p: que[u])
ans[p.se] = check(p.fi);
if (son[u]) skip[son[u]] = 0;
if (!keep)
edt(u);
}

int main() {
//    freopen("in.txt", "r", stdin);
scanf("%d%d", &n, &m);
for (int i = 2; i <= n; i++) {
int x;
scanf("%d", &x);
G[x].push_back(i);
}
scanf("%s", s + 1);
for (int i = 1, u, h; i <= m; i++) {
scanf("%d%d", &u, &h);
que[u].push_back(std::pii(h, i));
}
dfs1(1, 1);
dfs(1);
for (int i = 1; i <= m; i++)
puts(ans[i] ? "Yes" : "No");
return 0;
}```
View Code

Sgu507

```#include <bits/stdc++.h>

namespace IO {
template <typename T, typename... T2>
inline void read(T &x, T2 &... oth) {
T f = 1; x = 0;
char ch = getchar();
while (!isdigit(ch)) { if (ch == ‘-‘) f = -1; ch = getchar(); }
while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); }
x *= f;
}
} // using namespace IO
#define print IO::print
#define flush IO::flush

const int N = 1e5 + 7;
const int INF = 2147483647;
std::vector<int> vec[N];
std::set<int> st[N];
int n, m, color[N], ans[N];

int merge(int u, int v) {
if (st[u].size() < st[v].size())
std::swap(st[u], st[v]);
int res = INF;
for (std::set<int>::iterator it = st[v].begin(); it != st[v].end(); it++) {
auto i = st[u].lower_bound(*it);
if (i == st[u].begin()) {
res = std::min(res, *i - *it);
} else if (i == st[u].end()) {
i--;
res = std::min(res, *it - *i);
} else {
res = std::min(res, *i - *it);
i--;
res = std::min(res, *it - *i);
}
st[u].insert(*it);
}
st[v].clear();
return res;
}

void dfs(int u) {
ans[u] = INF;
if (vec[u].size() == 0) {
st[u].insert(color[u]);
return;
}
for (int v: vec[u]) {
dfs(v);
ans[u] = std::min(ans[u], ans[v]);
ans[u] = std::min(ans[u], merge(u, v));
}
}

int main() {
for (int i = 2; i <= n; i++) {
int u;
vec[u].push_back(i);
}
for (int i = n - m + 1; i <= n; i++)
dfs(1);
for (int i = 1; i <= n - m; i++)
printf("%d%c", ans[i], " \n"[i == n - m]);
return 0;
}```
View Code

HackerEarth, The Grass Type

```#include <bits/stdc++.h>
#define ll long long

const int N = 1e5 + 7;
std::map<int, int> mp[N];
int n, val[N];
std::vector<int> vec[N];
ll ans;

void merge(int u, int v) {
if (mp[u].size() < mp[v].size()) std::swap(mp[u], mp[v]);
for (auto p: mp[v]) {
if (val[u] % p.first == 0)
ans += 1LL * p.second * mp[u][val[u] / p.first];
}
for (auto p: mp[v])
mp[u][p.first] += p.second;
mp[v].clear();
}

void dfs(int u, int fa) {
mp[u][val[u]] = 1;
for (int v: vec[u]) {
if (v == fa) continue;
dfs(v, u);
merge(u, v);
}
}

int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
vec[u].push_back(v);
vec[v].push_back(u);
}
for (int i = 1; i <= n; i++)
scanf("%d", val + i);
dfs(1, 0);
printf("%lld\n", ans);
return 0;
}```
View Code

246E - Blood Cousins Return

```#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second

const int N = 1e5 + 7;
char s[N][22];
std::vector<int> vec[N];
std::vector<std::pii> query[N];
std::map<std::string, int> mp[N];
int n, son[N], sz[N], dep[N], ans[N], root, cnt[N];
bool skip[N];

void dfs1(int u, int d) {
sz[u] = 1;
dep[u] = d;
son[u] = -1;
for (int v: vec[u]) {
dfs1(v, d + 1);
sz[u] += sz[v];
if (son[u] == -1 || sz[son[u]] < sz[v]) son[u] = v;
}
}

void edt(int u, int k) {
mp[dep[u]][s[u]] += k;
int w = mp[dep[u]][s[u]];
if (k == 1 && w == 1) cnt[dep[u]]++;
if (k == -1 && w == 0) cnt[dep[u]]--;
assert(cnt[dep[u]] >= 0);
for (int v: vec[u])
if (!skip[v])
edt(v, k);
}

void dfs(int u, bool keep = 0) {
for (int v: vec[u])
if (v != son[u])
dfs(v);
if (son[u] != -1)
dfs(son[u], 1), skip[son[u]] = 1;
edt(u, 1);
for (auto p: query[u])
ans[p.se] = cnt[dep[u] + p.fi];
if (son[u] != -1)
skip[son[u]] = 0;
if (!keep)
edt(u, -1);
}

int main() {
scanf("%d", &n);
for (int i = 1, u; i <= n; i++) {
scanf("%s%d", s[i], &u);
vec[u].push_back(i);
}
int m;
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
int u, k;
scanf("%d%d", &u, &k);
query[u].push_back(std::pii(k, i));
}
dfs1(0, 0);
dfs(0, 1);
for (int i = 1; i <= m; i++)
printf("%d\n", ans[i]);
return 0;
}```
View Code

208E - Blood Cousins

```#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second

const int N = 1e5 + 7;
int dep[N], son[N], sz[N], n, fa[N][20], ans[N];
bool skip[N];
std::vector<int> vec[N];
std::vector<std::pii> query[N];

void dfs1(int u, int pre = 0, int d = 0) {
dep[u] = d;
fa[u][0] = pre;
for (int i = 1; i <= 18; i++) {
fa[u][i] = fa[fa[u][i - 1]][i - 1];
if (!fa[u][i]) break;
}
sz[u] = 1;
son[u] = -1;
for (int v: vec[u]) {
dfs1(v, u, d + 1);
sz[u] += sz[v];
if (son[u] == -1 || sz[son[u]] < sz[v])
son[u] = v;
}
}

int jump(int u, int k) {
for (int i = 18; ~i; i--)
if (k >> i & 1)
u = fa[u][i];
return u;
}

int cnt[N];

void edt(int u, int k) {
cnt[dep[u]] += k;
for (int v: vec[u])
if (!skip[v])
edt(v, k);
}

void dfs(int u, bool keep = 0) {
for (int v: vec[u])
if (v != son[u])
dfs(v);
if (son[u] != -1)
dfs(son[u], 1), skip[son[u]] = 1;
edt(u, 1);
for (auto p: query[u]) {
ans[p.se] = cnt[dep[u] + p.fi] - 1;
}
if (son[u] != -1)
skip[son[u]] = 0;
if (!keep)
edt(u, -1);
}

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int u;
scanf("%d", &u);
vec[u].push_back(i);
}
int m;
scanf("%d", &m);
dfs1(0);
for (int i = 1; i <= m; i++) {
int u, k;
scanf("%d%d", &u, &k);
u = jump(u, k);
if (u) query[u].push_back(std::pii(k, i));
}
dfs(0, 1);
for (int i = 1; i <= m; i++)
printf("%d%c", ans[i], " \n"[i == m]);
return 0;
}```
View Code