要善于把握算法的本质, 和使用的情景

懵逼的 题目

qwq

扯淡的 题解

当时的想法是….在dfs的时候…我找到一个点…就把他所有入度的LCA之上的点的答案都加一…然后想到树剖…结果rqy把这个想法hack了23333
因为在dfs(或者说拓扑排序)的时候你的树还没有建好…谈不上树剖…网上有说什么动态树剖的感觉非常神
那我们考虑找一个能在不断在下方添加节点的情况下还能求LCA的算法…就是倍增了…

还有一个挺巧妙的地方就是把这个节点挂在他所有入度的LCA下面, 这样就可以更快的统计答案了(据说这玩意叫支配树?)…

沙茶的 代码

又忘了在倍增LCA的时候判断是不是deep[x] == deep[y]x == y了…

/**************************************************************
    Problem: 2815
    User: Cansult
    Language: C++
    Result: Accepted
    Time:404 ms
    Memory:31560 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#define MAXN (100000 + 5)
#define MAXM (500000 + 5)
#define MAXL (20 + 5)
const int root = 0;
using namespace std;
struct edg
{
    int from, to, next;
}b[MAXM << 1], bn[MAXN << 1];
int g[MAXN], cntb, n, gn[MAXN], cntn, size[MAXN], du[MAXN], d[MAXN][MAXL], lgn, ans[MAXN], deep[MAXN];
vector<int> fa[MAXN];
int lg(int x)
{
    int re = 0;
    for (; (1 << re) <= x; ++re)
        continue;
    return re;
}
void adn(edg* bx, int* gx, int& cntx, int from, int to)
{
    bx[++cntx].next = gx[from];
    bx[cntx].from = from, bx[cntx].to = to;
    gx[from] = cntx;
}
int lca(int x, int y)
{
    if (deep[x] < deep[y])
        swap(x, y);
    for (int i = lgn; i >= 0; i--)
        if (deep[d[x][i]] >= deep[y])
            x = d[x][i];
    if (x == y)
        return x;
    for (int i = lgn; i >= 0; i--)
        if (d[x][i] != d[y][i])
            x = d[x][i], y = d[y][i];
    return d[x][0];
}
void init()
{
    queue<int> q;
    fa[root].push_back(root);
    deep[root] = 1;
    d[root][0] = 1;
    q.push(root);
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        int dqfa = fa[dq][0];
        for (int i = 1; i < fa[dq].size(); i++)
            dqfa = lca(dqfa, fa[dq][i]);
        d[dq][0] = dqfa;
        deep[dq] = deep[dqfa] + 1;
        adn(bn, gn, cntn, dqfa, dq);
        adn(bn, gn, cntn, dq, dqfa);
        for (int i = 1; i <= lgn; i++)
            d[dq][i] = d[d[dq][i - 1]][i - 1];
        for (int i = g[dq]; i; i = b[i].next)
        {
            fa[b[i].to].push_back(dq);
            du[b[i].to]--;
            if (!du[b[i].to])
                q.push(b[i].to);
        }
    }
}
void dfs(int dq, int fa)
{
    ans[dq] = 1;
    for (int i = gn[dq]; i; i = bn[i].next)
        if (bn[i].to != fa)
        {
            dfs(bn[i].to, dq);
            ans[dq] += ans[bn[i].to];
        }
}
int main()
{
    scanf("%d", &n);
    lgn = lg(n);
    for (int i = 1; i <= n; i++)
    for (int srx; ; )
    {
        scanf("%d", &srx);
        if (!srx)
            break;
        adn(b, g, cntb, srx, i);
        ++du[i];
    }
    for (int i = 1; i <= n; i++)
        if (!du[i])
        {
            ++du[i];
            adn(b, g, cntb, root, i);
        }
    init();
    dfs(root, root);
    for (int i = 1; i <= n; i++)
        printf("%d\n", ans[i] - 1);
    return 0;
}

By zz Cansult