题解：P9052 [PA 2021] Areny

好题，但是也没有那么难，感觉难度很大一部分在于读懂题。

题意：给出一个有向图，保证每个点都有一个出度且不为自环，现在求出对于每个 \(1\le k\le n\)，满足以下条件的 \((A,B)\) 对有多少个。

• \(1\le A\le k,A\not=B\)。
• 从 \(A\) 的任意一条路径，可以经过重复点，一定经过 \(B\)。

做法：

首先可以先转化一下，变成如果我路径经过 \(>k\) 的点路径就立马结束。那么就等于我把起点 \(>k\) 的边 ban 掉了。

先考虑 \(k=n\) 怎么做，我们对于一组 \((u,v)\) 满足 \(u\) 的路径必须经过 \(v\) 称其为“\(u\) 控制 \(v\)”，记为 \(u\to v\)。

发现这个东西很类似于支配对，所以我们也可以类似得出一些结论：

• 如果 \(u\) 的出边终点 \(v_1,v_2\cdots v_k\) 满足 \(v_1\to w,v_2\to w,\cdots v_k\to w\)，那么会有 \(u\to w\)。
• 如果 \(u\to v,v\to w\)，那么 \(u\to w\)。
• 如果 \(u\to v_1,v\to v_2\)，那么 \(v_1\to v_2\) 或者 \(v_2\to v_1\)。

都比较自然，很好理解。

发现这个东西满足，如果一个点控制两个点，那么我们完全没有必要同时建出来这两条边，只用建出来一条就可以。显然这样的控制关系最后一定会形成一个内向树或者内向基环树。

考虑怎么求出这个图。我们考虑根据第一个性质去构图，发现这样每个树连通块只有根还有出度，基环树则没有出度。如果一个节点 \(u\) 满足其出边都在一个连通块内，那么我们就建出一条 \(u\to w\) 的边，这个 \(w\) 要满足 \(v_1\to w,v_2\to w\cdots v_k\to w\)，就意味着 \(w\) 得是这些点在树上的 lca 即可。

分两种情况讨论，一种是 \(w\) 不在 \(u\) 的连通块，那么我们合并两个连通块。

否则我们就连出了一个环，我们直接暴力重新计算连通块的答案，因为每个点只会被重构一次，所以复杂度是有保证的。

现在的问题是怎么找到满足条件的 \(u\)，我们每个节点维护一个 \(v\) 所在连通块颜色的集合，在合并的时候就启发式合并，枚举终点在集合中的边然后去更新起点的出边集合，如果更新后大小为 \(1\) 就再接着更新。

然后考虑怎么对于所有的 \(k\) 计算答案，我们考虑对于 \(k=1\to n\) 逐步维护，每次加入 \(u\le k\) 且出边终点都满足 \(v\le k\) 的点 \(u\) 标为可加边，因为需要逐步加边，所以需要用 LCT 维护一下。

答案计算就是所有节点到根的点权和，对于连出来环，比较方便的方式是直接把根到 \(w\) 的路径上点权全部置为 \(0\)，然后把根的权值置为路径长度。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5;
int n;
vector<int> e[maxn], bk[maxn], g[maxn], pos[maxn];
set<int> s[maxn];
int pre[maxn], sz[maxn];
void prepare() {for (int i = 1; i <= n; i++)pre[i] = i, sz[i] = 1;
}
int fnd(int x) {return (pre[x] == x ? x : pre[x] = fnd(pre[x]));
}struct node {int son[2], fa, val, res;
} ;
struct LCT {node tr[maxn];#define ls(x) tr[x].son[0]#define rs(x) tr[x].son[1]#define fa(x) tr[x].fabool get(int x) {return rs(fa(x)) == x;}bool isroot(int x) {return ls(fa(x)) != x  && rs(fa(x)) != x;}void pushup(int x) {tr[x].res = tr[ls(x)].res + tr[rs(x)].res + tr[x].val;}void rotate(int x) {int y = fa(x), z = fa(y), k = get(x);if(!isroot(y))tr[z].son[get(y)] = x;tr[y].son[k] = tr[x].son[1 - k];fa(tr[x].son[1 - k]) = y;tr[x].son[1 - k] = y;fa(x) = z, fa(y) = x;pushup(y), pushup(x);}void splay(int x) {while(!isroot(x)) {if(!isroot(fa(x)) && get(x) == get(fa(x)))rotate(fa(x));rotate(x);}}int access(int x) {int pre = 0;while(x) {splay(x);rs(x) = pre; fa(pre) = x;pushup(x);pre = x, x = fa(x);}return pre;}int lca(int x, int y) {access(x);return access(y);}int query(int x) {access(x); splay(x);return tr[x].res;}int dfs2(int u, int id) {int val = 1;tr[u].val = 0;if(ls(u))val += dfs2(ls(u), id);if(rs(u))val += dfs2(rs(u), id);if(u == id)tr[u].val = val;pushup(u);return val;	}
} tree;
int use[maxn], vis[maxn], res;
void dfs1(int u, vector<int> &pos) {pos.push_back(u);for (int i = 0; i < g[u].size(); i++) {int v = g[u][i];dfs1(v, pos);}
}
void solve(int u) {if(!use[u] || vis[u])return ;vis[u] = 1;int rtu = fnd(u), rtv = fnd(*s[u].begin());if(rtu != rtv) {tree.access(u), tree.splay(u);int nw = e[u][0];for (int i = 1; i < e[u].size(); i++)nw = tree.lca(nw, e[u][i]);g[nw].push_back(u); tree.tr[u].fa = nw;res += sz[rtu] * tree.query(nw);//	cout << u << " adsf" << sz[rtu] * tree.query(nw) << " " << res << endl;if(sz[rtu] > sz[rtv])swap(rtu, rtv);pre[rtu] = rtv, sz[rtv] += sz[rtu];vector<int> nxt;for (int i = 0; i < pos[rtu].size(); i++) {pos[rtv].push_back(pos[rtu][i]);int p = pos[rtu][i];for (int j = 0; j < bk[p].size(); j++) {s[bk[p][j]].erase(rtu);s[bk[p][j]].insert(rtv);if(s[bk[p][j]].size() == 1)nxt.push_back(bk[p][j]);}}for (int i = 0; i < nxt.size(); i++)solve(nxt[i]);return ;}
//	cout << u << " lsakjfhaf" << res << " " << tree.tr[5].fa << endl;int nw = e[u][0];for (int i = 1; i < e[u].size(); i++)nw = tree.lca(nw, e[u][i]);
//	cout << nw << endl;vector<int> pos;dfs1(u, pos);
//	cout << res << " " << nw << " " << tree.tr[5].son[0] << " " << tree.tr[5].son[1] << endl;for (int i = 0; i < pos.size(); i++)res -= tree.query(pos[i]);tree.access(nw);tree.splay(u);tree.dfs2(u, u);for (int i = 0; i < pos.size(); i++)res += tree.query(pos[i]);
}
vector<int> vec[maxn];
signed main() {cin >> n;for (int i = 1; i <= n; i++) {int k, mx = i; cin >> k; pos[i].push_back(i);while(k--) {int x; cin >> x;e[i].push_back(x), bk[x].push_back(i);s[i].insert(x);mx = max(mx, x);}tree.tr[i].val = tree.tr[i].res = 1;vec[mx].push_back(i);}prepare();for (int i = 1; i <= n; i++) {for (int j = 0; j < vec[i].size(); j++) {use[vec[i][j]] = 1;if(s[vec[i][j]].size() == 1)solve(vec[i][j]);}cout << res << " ";}cout << endl;return 0;
}
/*
5
4 2 3 4 5
3 3 4 5
2 4 5
1 5
1 1
*/