tarjan，找环

比赛时先看错了题，然后，想出来方案再到编码没赶上。
coding还是太慢了。要刻意练习。

关键信息在于n个节点n条边。
我们注意到了，这其实就是一棵树再加上一条边。
树中形成了一个环。
我们把这个环单独拿出来，将其他节点视作有这个环上的节点向外的延申。
也就是以这个环的每一个节点为根生成了一个又一个的树。
我们可以统计每个树的简单路径，然后再统计经过了这个环后的简单路径。
如何统计经过了这个环后的简单路径呢？
我们注意到经过这个环，那么这条路径的两个端点一定是在不同的树中，而因为是环
所以对于同样的起点终点我们有两条不同的路径。
故，算法完毕。

但是，麻烦的事来了。
我们如何找到这个环呢？
利用类似tajian的做法，一边dfs一边染色，同时人工模仿一个栈。
代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int max_n = 2e5+100;
typedef long long ll;
struct edge{
    int to,next;
}E[max_n<<1];
int head[max_n];
int cnt=1;
void add(int from,int to){
    E[cnt].to=to;E[cnt].next=head[from];
    head[from] = cnt++;
}
vector<int> v,stack;
bool f = true;
bool vis[max_n];
void dfs(int u,int fa){
    vis[u]=true;
    stack.push_back(u);
    for (int i=head[u];i;i=E[i].next){
        int vv = E[i].to;
        if (vv==fa)continue;
        else if (vis[vv]){
            while (stack.back()!=vv){
                v.push_back(stack.back());
                stack.pop_back();
            }v.push_back(vv);
            f = false;
            return;
        }
        else{
            dfs(vv,u);
            if (!f)return;
            else stack.pop_back();
        }
    }
}
bool used[max_n];
ll cct[max_n];
ll Dfs(int u,int fa){
    ll ans =1;
    for (int i=head[u];i;i=E[i].next){
        int v = E[i].to;
        if (v==fa||used[v])continue;
        ll tmp=Dfs(v,u);
        ans+=Dfs(v,u);
    }return cct[u]=ans;
}
ll ddfs(int u,int fa){
    vector<ll> tmp;
    ll ans = 0;ll sum=0;
    for (int i=head[u];i;i=E[i].next){
        int v = E[i].to;
        if (v==fa||used[v])continue;
        tmp.push_back(cct[v]);
        ans+=ddfs(v,u);
        ans+=cct[v];
        sum+=cct[v];
    }
    ll ttt = 0;
    for (int num:tmp)ttt+=num*(sum-num);
    ttt>>=1;
    ans+=ttt;
    return ans;
}
ll ans = 0;
int n;
int main(){
    int t;scanf("%d",&t);
    while (t--){
        f=true;ans = 0;
        stack.clear(),v.clear();
        int n;scanf("%d",&n);
        fill(head,head+n+10,0);cnt=1;
        fill(vis,vis+n+10,0);
        fill(used,used+n+10,0);
        fill(cct,cct+n+10,0);
        for (int i=1,u,v;i<=n;++i){
            scanf("%d %d",&u,&v);
            add(u,v);add(v,u);
        }
        dfs(1,0);
        for (int aa:v)used[aa]=true;
        vector<ll> res;ll sum = 0;
        for (int i=0;i<v.size();++i){
            Dfs(v[i],0);sum+=cct[v[i]];
            res.push_back(cct[v[i]]);
        }
        for (int i=0;i<v.size();++i){
            ans+=ddfs(v[i],0);
        }
        for (int i=0;i<res.size();++i){
            ans+=res[i]*(sum-res[i]);
        }
        printf("%lld\n",ans);
    }
}