#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define db long double
#define ii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define FN(i, n) for (int i = 0; i < (int)(n); ++i)
#define FEN(i,n) for (int i = 1;i <= (int)(n); ++i)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repv(i,a,b) for(int i=b-1;i>=a;i--)
#define SET(A, val) memset(A, val, sizeof(A))
typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const int N=100005;
vi v[N];
bool vis[N];
ll ans;
int n,m;
//for subtask 1,2
bool mark[N];
//for subtask 4,5
ll sumd[N]; int d[N],child[N];
bool checksub12()
{
if(n>50) return false;
function<void (int,int,int,vi&) > dfs = [&](int u,int s,int f,vi &tmp)->void
{
if(u==f)
{
for(int x:tmp) mark[x]=true;
return;
}
vis[u]=true;
tmp.pb(u);
for(int v1:v[u]) if(!vis[v1]) dfs(v1,s,f,tmp);
tmp.pop_back();
vis[u]=false;
};
rep(i,1,n+1)
rep(j,i+1,n+1)
{
rep(k,1,n+1) mark[k]=false;
vi tmp;
dfs(i,i,j,tmp);
rep(k,1,n+1)
if(k!=i && k!=j && mark[k]) ans+=2;
}
cout<<ans<<endl;
return true;
}
bool checksub3()
{
bool sub3=true;
rep(i,1,n+1) if(sz(v[i])>2) sub3=false;
if(!sub3) return false;
function<void (int, vi&)> dfs = [&](int u,vi &tmp)->void
{
vis[u]=true; tmp.pb(u);
for(int v1:v[u]) if(!vis[v1]) dfs(v1,tmp);
};
memset(vis,false,sizeof(vis));
rep(i,1,n+1)
{
if(vis[i]) continue;
vi tmp;
dfs(i,tmp);
bool chain=false;
for(int x:tmp) if(sz(v[x])==1) chain=true;
int tot=sz(tmp);
if(!chain) ans+=(ll)(tot-2)*(ll)tot*(tot-1);
else rep(j,1,tot-1) ans+=((ll)j*(j+1));
}
cout<<ans<<endl;
return true;
}
bool checksub45()
{
function<bool (int, int)> dfs = [&](int u,int par)->bool
{
child[u]=1;
vis[u]=true;
for(int v1:v[u])
{
if(v1==par) continue;
if(vis[v1]) return false;
d[v1]=d[u]+1;
dfs(v1,u);
child[u]+=child[v1];
}
return true;
};
function<void (int, int)> dfs2 = [&](int u,int par)->void
{
vis[u]=true;
for(int v1:v[u])
{
if(v1==par) continue;
dfs2(v1,u);
sumd[u]+=sumd[v1];
}
for(int v1:v[u])
{
if(v1==par) continue;
ans+=(ll)(child[u]-child[v1]-1)*(ll)sumd[v1];
ans+=(ll)child[v1]*(ll)(sumd[u]-sumd[v1]);
ans-=(ll)child[v1]*(child[u]-(ll)child[v1]-1)*(ll)(d[u]*2+1);
}
ans+=(ll)(sumd[u]-(ll)(child[u]-1)*(ll)(d[u]+1))*(ll)2;
sumd[u]+=d[u];
};
rep(i,1,n+1)
{
if(vis[i]) continue;
if(!dfs(i,-1)) return false;
}
memset(vis,false,sizeof(vis));
rep(i,1,n+1)
{
if(vis[i]) continue;
dfs2(i,-1);
}
cout<<ans<<endl;
return true;
}
namespace bt//bridge tree
{
const int N=200005;
vi v[N],tree[N],nodes[N];
int a[N],b[N],low[N],st[N],d[N],timer,cno=1,child[N],child2[N];
ll sumd[N],sumd2[N];
bool bridge[N],vis[N],mark[N];
queue<int> Q[N];
ll ans=0;
void findbridges(int u,int par=-1)
{
vis[u]=true;
low[u]=st[u]=timer++;
for(int ind:v[u])
{
if(ind==par) continue;
int v1=(a[ind]^b[ind]^u);
if(vis[v1]) low[u]=min(low[u],st[v1]);
else
{
findbridges(v1,ind);
low[u]=min(low[u],low[v1]);
if(low[v1]>st[u])
bridge[ind]=true;
}
}
}
void dfs(int u)
{
int curr=cno;
Q[curr].push(u);
nodes[curr].pb(u);
vis[u]=true;
while(!Q[curr].empty())
{
u=Q[curr].front();
Q[curr].pop();
for(int ind:v[u])
{
if(mark[ind]) continue;
int v1=(a[ind]^b[ind]^u);
mark[ind]=true;
if(vis[v1])
continue;
if(bridge[ind])
{
cno++;
tree[curr].pb(cno);
tree[cno].pb(curr);
dfs(v1);
}
else
{
Q[curr].push(v1);
nodes[curr].pb(v1);
vis[v1]=true;
}
}
}
}
void dfstree(int u)
{
child[u]=sz(nodes[u]);
child2[u]=1;
d[u]+=sz(nodes[u]);
vis[u]=true;
for(int v1:tree[u])
{
if(vis[v1]) continue;
d[v1]+=d[u];
dfstree(v1);
child[u]+=child[v1];
child2[u]+=child2[v1];
}
}
void dfstree2(int u)
{
vis[u]=true;
for(int v1:tree[u])
{
if(vis[v1]) continue;
dfstree2(v1);
sumd[u]+=sumd[v1];
sumd2[u]+=sumd2[v1];
}
int sz=sz(nodes[u]);
for(int v1:tree[u])
{
if(vis[v1]) continue;
ans+=(ll)(child[u]-child[v1]-sz)*(ll)sumd[v1];
ans+=(ll)child[v1]*(ll)(sumd[u]-sumd[v1]);
ans-=(ll)child[v1]*(child[u]-(ll)child[v1]-sz)*(ll)(d[u]*2+2-sz);
//remove answer for corner points
ans-=(ll)(child[u]-child[v1]-sz)*sumd2[v1];
ans-=(ll)child2[v1]*(ll)(sumd[u]-sumd[v1]);
ans+=(ll)child2[v1]*(child[u]-(ll)child[v1]-sz)*(ll)(d[u]*2+2-sz);
//add answer when v1's corner point,but not on other
ans+=(ll)(child[u]-child[v1]-sz-(child2[u]-child2[v1]-1))*(ll)(sumd2[v1]-child[v1]);
ans+=(ll)child2[v1]*(ll)(sumd[u]-sumd[v1]-(sumd2[u]-sumd2[v1]));
ans-=(ll)child2[v1]*(ll)(child[u]-child[v1]-sz-(child2[u]-child2[v1]-1))*(ll)(d[u]*2+1-sz);
//add answer when both corner points
ans+=(ll)(child2[u]-child2[v1]-1)*(ll)(sumd2[v1]-child[v1]);
ans+=(ll)child2[v1]*(ll)(sumd2[u]-sumd2[v1]-(child[u]-child[v1]-sz));
ans-=(ll)child2[v1]*(ll)(child2[u]-child2[v1]-1)*(ll)(d[u]*2-sz);
}
ll tmp=0;
//add answer for root
tmp+=(ll)sz*sumd[u];
tmp-=((ll)(child[u]-sz)*(ll)sz*(ll)(d[u]+2-sz));
//if(u==2) trace(tmp);
//remove answer for corner point
tmp-=sz*sumd2[u];
tmp+=((ll)(child2[u]-1)*(ll)sz*(ll)(d[u]+2-sz));
//if(u==2) trace(tmp);
//add answer when v1's corner point,but not on other
tmp+=(ll)(sz-1)*(sumd2[u]-(child[u]-sz));
tmp-=((ll)(child2[u]-1)*(ll)(sz-1)*(ll)(d[u]+1-sz));
//if(u==2) trace(tmp);
//add answer when both corner points
tmp+=(sumd2[u]-(child[u]-sz));
tmp-=((ll)(child2[u]-1)*(ll)d[u]);
//if(u==2) trace(tmp,sumd2[u],child[u],child2[u]);
ans+=tmp*(ll)2;
//add answer for within the node
ans+=(ll)sz*(ll)(sz-1)*(ll)(sz-2);
//trace(u,ans);
sumd[u]+=(ll)d[u]*sz;
sumd2[u]+=d[u];
}
};
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(NULL) ; cout.tie(NULL) ;
cin>>n>>m;
rep(i,1,m+1)
{
int x,y;
cin>>x>>y;
v[x].pb(y); v[y].pb(x);
bt::a[i]=x; bt::b[i]=y;
bt::v[x].pb(i); bt::v[y].pb(i);
}
//if(checksub12()) return 0;//brute
//if(checksub45()) return 0;// a tree
//if(checksub3()) return 0; //degree at most 2
rep(i,1,n+1)
{
if(bt::vis[i]) continue;
bt::findbridges(i);
}
rep(i,1,n+1) bt::vis[i]=false;
rep(i,1,n+1)
{
if(bt::vis[i]) continue;
bt::dfs(i);
bt::cno++;
}
rep(i,1,n+1) bt::vis[i]=false;
rep(i,1,n+1)
{
if(bt::vis[i]) continue;
bt::dfstree(i);
}
rep(i,1,n+1) bt::vis[i]=false;
rep(i,1,bt::cno+1)
{
if(bt::vis[i]) continue;
bt::dfstree2(i);
}
cout<<bt::ans<<endl;
return 0 ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
139 ms |
151544 KB |
Output is correct |
| 2 |
Correct |
144 ms |
151736 KB |
Output is correct |
| 3 |
Correct |
143 ms |
151736 KB |
Output is correct |
| 4 |
Incorrect |
143 ms |
151736 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
139 ms |
151544 KB |
Output is correct |
| 2 |
Correct |
144 ms |
151736 KB |
Output is correct |
| 3 |
Correct |
143 ms |
151736 KB |
Output is correct |
| 4 |
Incorrect |
143 ms |
151736 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
291 ms |
169248 KB |
Output is correct |
| 2 |
Correct |
331 ms |
169248 KB |
Output is correct |
| 3 |
Incorrect |
320 ms |
171616 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
143 ms |
171616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
335 ms |
171616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
154 ms |
171616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
312 ms |
171616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
139 ms |
151544 KB |
Output is correct |
| 2 |
Correct |
144 ms |
151736 KB |
Output is correct |
| 3 |
Correct |
143 ms |
151736 KB |
Output is correct |
| 4 |
Incorrect |
143 ms |
151736 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
139 ms |
151544 KB |
Output is correct |
| 2 |
Correct |
144 ms |
151736 KB |
Output is correct |
| 3 |
Correct |
143 ms |
151736 KB |
Output is correct |
| 4 |
Incorrect |
143 ms |
151736 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
