首先%%%lydrainbowcat
这个题唔，真是Tarjan好题（？）
不知道为啥也叫BLO，首字母？
<题面>
搜索树真真的棒！
仔细看看，知道是Tarjan了，切掉一个点有不通的对数，明显求割点。
$langle i,j angle$和$langle j,i angle$是不一样的
一边统计搜索树上的$size$
然后在割点的出边统计
下面是重点：
首先定义$sum_i$为子树$i$上的$size$总和，$pre_i$为$i$的父亲节点，$pn$为总点数
如果
1.搜到了儿子
1）$low_s<low_i(s in son_i)$绝对儿子，直接加
用$size_s imes (pn-size_s)$统计对答案贡献(思考思考)
2）$low_s=low_i(s in son_i)$考虑一下
必须在搜索树上$pre$为$i$才能统计
不然不加重就是数据炸了（事实证明数据不是很水）
2.是父亲
先跳过，等会统计完$sum_i$自然可求
统计完了，把$(pn-sum_i-1)*sum_i$加进去，发现少点什么，
把$pn-1$加进去，即为$i$号点的出对$langle i,n angle(n eq i)$
快乐水果～
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <vector> 5 #define N 111111 6 #define M 505505 7 #define LL long long 8 using namespace std; 9 struct SR { 10 int f, next, t; 11 } rs[M * 2]; 12 int fl[N], cnt = 0; 13 int pn, edn; 14 inline int Max(const int a, const int b) { 15 if (a > b) 16 return a; 17 return b; 18 } 19 inline int Min(const int a, const int b) { 20 if (a < b) 21 return a; 22 return b; 23 } 24 void add(int f, int t) { 25 rs[cnt].f = f, rs[cnt].t = t, rs[cnt].next = fl[f]; 26 fl[f] = cnt; 27 cnt++; 28 } 29 int dfn[N], low[N], dep = 0, siz[N], pres[N]; 30 bool is_totop[N], is_v[N], is_cut[N]; 31 LL ans[N], ros = 0; 32 void tarjan(int k, int pre) { 33 dep++; 34 siz[k] = 1; 35 dfn[k] = low[k] = dep; 36 pres[k] = pre; 37 for (int i = fl[k]; i != -1; i = rs[i].next) { 38 int t = rs[i].t; 39 if (!dfn[t]) { 40 tarjan(t, k); 41 low[k] = Min(low[k], low[t]); 42 siz[k] += siz[t]; 43 if (k == 1) 44 ros++; 45 if (low[t] >= dfn[k]) 46 is_cut[k] = 1; 47 } else { 48 if (low[k] > dfn[t] && t != pre) { 49 low[k] = dfn[t]; 50 } 51 } 52 } 53 } 54 LL calc(int k) { // cout<<"Cut"<<k<<endl; 55 LL aan = 0, sum = 0; 56 for (int i = fl[k]; i != -1; i = rs[i].next) { 57 int t = rs[i].t; 58 if (low[t] > dfn[k]) { 59 aan += (LL)siz[t] * (pn - siz[t]); 60 sum += siz[t]; 61 } else if (low[t] == dfn[k] && pres[t] == k) { 62 aan += (LL)siz[t] * (pn - siz[t]); 63 sum += siz[t]; 64 } 65 } 66 return aan + pn - 1 + (LL)((LL)pn - 1 - sum) * (1 + (LL)sum); 67 } 68 int main() { 69 int a, b; 70 memset(fl, -1, sizeof fl); 71 scanf("%d%d", &pn, &edn); 72 for (int i = 1; i <= edn; i++) { 73 scanf("%d%d", &a, &b); 74 add(a, b); 75 add(b, a); 76 } 77 tarjan(1, 1); 78 if (ros <= 1) 79 ans[1] = (LL)(pn - 1) * 2; 80 else 81 ans[1] = calc(1); 82 for (int i = 2; i <= pn; i++) { 83 if (is_cut[i]) { 84 ans[i] = calc(i); 85 } else { 86 ans[i] = (LL)(pn - 1) * 2; 87 } 88 } 89 for (int i = 1; i <= pn; i++) { 90 printf("%lld ", ans[i]); 91 } 92 return 0; 93 }