CF246E Blood Cousins Return 做题记录
我糖丸了，调了半天的 TLE，结果最后发现是自己写 dsu on tree 时就写错了。成功在统计时也只遍历重儿子，就这样还能对 9 个点。
森林这个特点无需在意，只要枚举一遍所有点看谁没访问过就可以了。
寻找 k-son 的话，我们先离线，将问题保存在对应的点的 vector 里，由于我感觉 set 的字符串作为下标更慢，所以用了个 unordered_map。然后我们直接开始 dfs，第一遍找重儿子，记录每个点的时间戳和每个时间戳对应的点（清空时循环比递归更快，统计按理来说也是一样，不过如果让重儿子就是当前点时间戳的下一位还要 dfs 一遍，更慢），然后我们给每个深度创一个 set，每个点的名字就保存在对应深度的 set 里，由于自动去重，所以当前点深度加查询深度的和的 vector 尺寸就是答案，剩下的只剩输出了。
总的来说难度不至于紫，这个恶作剧值得记住。
先是 dsu on tree 的代码（我去写一下莫队）：
//Just Sayori
#pragma GCC diagnostic ignored "-Wnarrowing"
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
#include <unordered_map>
#define ll long long
#define ull unsigned long long
#define rnt register int
#define gr getchar
#define pr putchar
#define N 200005
#define M 5000011
#define int long long
using namespace std;
inline ll read()
{
ll x = 0, f = 1;
char ch = gr();
while (ch < '0' || ch > '9') ch == '-' ? f = -1, ch = gr() : ch = gr();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = gr();
return x * f;
}
inline void write(ll x)
{
static int top = 0, sta[39];
if (x < 0) pr('-'), x = -x;
do sta[++top] = x % 10, x /= 10;
while (x);
while (top) pr(sta[top--] ^ 48);
}
struct edge
{
int v, next;
} e[N << 1];
int head[N], cnt;
inline void add(int u, int v)
{
e[++cnt] = {v, head[u]}, head[u] = cnt;
}
int n, m, u, k, mcnt;
int g[N], p[N], sz[N], ans[N], dfn[N], vis[N], bson[N], deep[N];
string s;
set<int> st[N];
vector<pair<int, int >> v[N];
unordered_map<string, int>mp;
void dfs1(int u, int f)
{
dfn[u] = ++cnt;
sz[u] = 1, g[cnt] = u;
deep[u] = deep[f] + 1;
for (rnt i = head[u]; i; i = e[i].next)
{
int v = e[i].v;
dfs1(v, u);
sz[u] += sz[v];
if (sz[v] > sz[bson[u]]) bson[u] = v;
}
}
void get(int u)
{
st[deep[u]].insert(p[u]);
for (rnt i = head[u]; i; i = e[i].next)
{
int v = e[i].v;
get(v);
}
}
void dfs2(int u, int k)
{
for (rnt i = head[u]; i; i = e[i].next)
{
int v = e[i].v;
if (v == bson[u]) continue;
dfs2(v, 0);
}
if (bson[u])
dfs2(bson[u], 1);
st[deep[u]].insert(p[u]);
for (rnt i = head[u]; i; i = e[i].next)
{
int v = e[i].v;
if (v == bson[u]) continue;
get(v);
}
int len = v[u].size();
for (rnt i = 0; i < len; i++)
ans[v[u][i].second] = st[deep[u] + v[u][i].first].size();
if (!k)
for (rnt i = dfn[u]; i <= dfn[u] + sz[u] - 1; i++)
st[deep[g[i]]].erase(p[g[i]]);
}
signed main()
{
cin.tie(0);
n = read();
for (rnt i = 1; i <= n; i++)
{
cin >> s ;
if (!mp[s]) mp[s] = ++mcnt;
p[i] = mp[s], add(read(), i);
}
cin >> m, cnt = 0;
for (rnt i = 1; i <= m; i++)
u = read(), k = read(), deep[u] + k <= n ? v[u].push_back(make_pair(k, i)) : void();
for (rnt i = 1; i <= n; i++)
if (!dfn[i])
dfs1(i, 0), dfs2(i, 0);
for (rnt i = 1; i <= m; i++)
write(ans[i]), pr(10);
return 0;
}写完了，甚至在没用我的逆天哈希表的情况下跑得更快（因为用了就 WA 了），代码：
//Just Sayori
#pragma GCC diagnostic ignored "-Wnarrowing"
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <set>
#include <unordered_map>
#define ll long long
#define ull unsigned long long
#define rnt register int
#define gr getchar
#define pr putchar
#define N 500005
#define M 1000000007
using namespace std;
inline ll read()
{
ll x = 0, f = 1;
char ch = gr();
while (ch < '0' || ch > '9') ch == '-' ? f = -1, ch = gr() : ch = gr();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = gr();
return x * f;
}
inline void write(ll x)
{
static int top = 0, sta[39];
if (x < 0) pr('-'), x = -x;
do sta[++top] = x % 10, x /= 10;
while (x);
while (top) pr(sta[top--] ^ 48);
}
struct edge
{
int v, next;
} e[N << 1];
int head[N], cnt;
inline void add(int u, int v)
{
e[++cnt] = {v, head[u]}, head[u] = cnt;
}
int n, m, l, r, len, tot;
string s;
int a[N], b[N], w[N], sz[N], ans[N], dfn[N], sum[N], deep[N];
unordered_map<string, int> ht;
unordered_map<int, int> mp[N];
void dfs(int u, int f)
{
sz[u] = 1;
dfn[u] = ++cnt;
w[cnt] = u;
deep[u] = deep[f] + 1;
for (rnt i = head[u]; i; i = e[i].next)
{
int v = e[i].v;
dfs(v, u);
sz[u] += sz[v];
}
}
struct node
{
int l, r, k, id, deep;
bool operator <(node o)
{
return b[l] ^ b[o.l] ? l < o.l : (b[l] & 1) ? r<o.r: r>o.r;
}
} q[N];
void add(int x)
{
x = w[x];
if (!(mp[deep[x]][a[x]]++))
sum[deep[x]]++;
}
void ded(int x)
{
x = w[x];
if (!(--mp[deep[x]][a[x]]))
sum[deep[x]]--;
}
int main()
{
cin.tie(0);
n = read(), len = sqrt(n);
for (rnt i = 1; i <= n; i++)
{
cin >> s;
if (!ht[s]) ht[s] = ++tot;
a[i] = ht[s], add(read(), i), b[i] = (i - 1) / len + 1;
}
cnt = 0;
for (rnt i = 1; i <= n; i++)
if (!dfn[i])
dfs(i, 0);
m = read();
for (rnt i = 1, x; i <= m; i++)
x = read(), q[i] = {dfn[x], dfn[x] + sz[x] - 1, read(), i, deep[x]};
sort(q + 1, q + m + 1), l = 1, r = 0;
for (rnt i = 1; i <= m; i++)
{
if (q[i].deep + q[i].k > n) continue;
while (q[i].r > r) add(++r);
while (q[i].l < l) add(--l);
while (q[i].r < r) ded(r--);
while (q[i].l > l) ded(l++);
ans[q[i].id] = sum[q[i].deep + q[i].k];
}
for (rnt i = 1; i <= m; i++)
write(ans[i]), pr(10);
return 0;
}我一定要把哈希表写出来！
……
……
……
……
……
……
……
……
……
……
……
……
……
好吧，T 了。