相关链接
题目传送门:https://www.codechef.com/problems/GRAPHCNT
数据生成器:http://paste.ubuntu.com/24319212/
神犇题解Ⅰ:http://blog.csdn.net/a710128/article/details/49913553
神犇题解Ⅱ:http://www.cnblogs.com/meowww/p/6475952.html
解题报告
就是支配树的板题?
我们可以用Lengauer Tarjan算法在$O(n \alpha (n))$的时间复杂度内解决这个问题
也可以求出所有的半支配点,然后用灭绝树来搞,时间复杂度:$O(n \log n)$
另外之前我还看到一种非常鬼畜地LCT+灭绝树地做法,时间复杂度跑起来像:$O(n \log n)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100009; const int M = 1500009; int n,m; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } class Dominator_Tree{ int dom[N],pre[N],head[N],nxt[M],to[M],que[N],anc[N]; int dfs_cnt,dfn[N],idom[N],semi[N],bst[N],ufs[N],sz[N]; public: inline void AddEdge(int u, int v) { AddEdge(head, u, v); AddEdge(pre, v, u); } inline void build() { DFS(1); for (int i=dfs_cnt,w;w=que[i],i>1;i--) { for (int j=pre[w];j;j=nxt[j]) { if (dfn[to[j]]) { update(to[j]); if (dfn[semi[bst[to[j]]]] < dfn[semi[w]]) semi[w] = semi[bst[to[j]]]; } } AddEdge(dom, semi[w], w); ufs[w] = anc[w]; w = que[i-1]; for (int j=dom[w];j;j=nxt[j]) { update(to[j]); if (semi[bst[to[j]]] == w) idom[to[j]] = w; else idom[to[j]] = bst[to[j]]; } } for (int i=2,w;w=que[i],i<=dfs_cnt;i++) idom[w] = ((idom[w] == semi[w])? idom[w]: idom[idom[w]]); } inline LL solve() { LL ret = dfs_cnt * (dfs_cnt - 1ll) / 2ll; for (int i=dfs_cnt,w;w=que[i],i>1;i--) { if (++sz[w], idom[w] != 1) sz[idom[w]] += sz[w]; else ret -= (sz[w] - 1ll) * sz[w] / 2ll; } return ret; } private: inline void AddEdge(int *arr, int u, int v) { static int E = 1; to[++E] = v; nxt[E] = arr[u]; arr[u] = E; } void DFS(int w) { dfn[w] = ++dfs_cnt; que[dfs_cnt] = w; bst[w] = semi[w] = ufs[w] = w; for (int i=head[w];i;i=nxt[i]) if (!dfn[to[i]]) anc[to[i]] = w, DFS(to[i]); } int update(int w) { if (ufs[w] == w) return w; int tmp = update(ufs[w]); if (dfn[semi[bst[ufs[w]]]] < dfn[semi[bst[w]]]) bst[w] = bst[ufs[w]]; return ufs[w] = tmp; } }DMT; int main() { n = read(); m = read(); for (int i=1,u,v;i<=m;i++) { u = read(); v = read(); DMT.AddEdge(u, v); } DMT.build(); cout<<DMT.solve(); return 0; }