简单来说就是把答案的计算方式换了一下,但是重复计算了一些答案。
把
.
aans[u] += 1ll*siz[v] * (n - siz[v]);
.
.
if(vis[u] == 0) ans[u] = 1ll*(n-1);
else ans[u] += 1ll*(n-sum-1);
.
.
.
ans[i] = 1ll*2*ans[i];
cout << ans[i] << "\n";
改为
.
ans[u] += 1ll*siz[v] * (n - siz[v]);
.
.
if(vis[u] == 0) ans[u] = 1ll*2*(n-1);
else ans[u] += 1ll*(n-sum-1)*(sum+1)+1ll*(n-1);
.
.
.
cout << ans[i] << "\n";
就过了
#include<bits/stdc++.h>
#define ll long long
#define Mid ll mid = (l+r)>>1
using namespace std;
const int N = 5e5 + 20;
ll n, m, tot = 0;
ll cnt = 1, h[N], siz[N], ans[N];
ll low[N], dfn[N];
bool vis[N];
struct graph{
ll v, nxt;
}e[N<<1];
void add_edge(ll u, ll v) {
e[++cnt] = (graph){v, h[u]};
h[u] = cnt;
}
void tarjan(ll u, ll inid) {
low[u] = dfn[u] = ++tot;
siz[u] = 1;
ll son = 0, sum = 0;
for(int i = h[u]; i; i = e[i].nxt) {
ll v = e[i].v;
if(i == (inid^1)) continue;
if(!dfn[v]) {
tarjan(v, i);
siz[u] += siz[v];
low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u]) {
sum += siz[v];
son++;
ans[u] += 1ll*siz[v] * (n - siz[v]);
if(u!=1 || son > 1) vis[u] = 1;
}
}
else low[u] = min(low[u], dfn[v]);
}
if(vis[u] == 0) ans[u] = 1ll*(n-1);
else ans[u] += 1ll*(n-sum-1);
}
int main(){
cin >> n >> m;
for(int i = 1; i <= m; i++) {
ll u, v;
cin >> u >> v;
add_edge(u, v);
add_edge(v, u);
}
tarjan(1, 0);
for(int i = 1; i <= n; i++) {
ans[i] = 1ll*2*ans[i];
cout << ans[i] << "\n";
}
return 0;
}
#include<bits/stdc++.h>
#define ll long long
#define Mid ll mid = (l+r)>>1
using namespace std;
const int N = 5e5 + 20;
ll n, m, tot = 0;
ll cnt = 1, h[N], siz[N], ans[N];
ll low[N], dfn[N];
bool vis[N];
struct graph{
ll v, nxt;
}e[N<<1];
void add_edge(ll u, ll v) {
e[++cnt] = (graph){v, h[u]};
h[u] = cnt;
}
void tarjan(ll u, ll inid) {
low[u] = dfn[u] = ++tot;
siz[u] = 1;
ll son = 0, sum = 0;
for(int i = h[u]; i; i = e[i].nxt) {
ll v = e[i].v;
if(i == (inid^1)) continue;
if(!dfn[v]) {
tarjan(v, i);
siz[u] += siz[v];
low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u]) {
sum += siz[v];
son++;
ans[u] += 1ll*siz[v] * (n - siz[v]);
if(u!=1 || son > 1) vis[u] = 1;
}
}
else low[u] = min(low[u], dfn[v]);
}
if(vis[u] == 0) ans[u] = 1ll*2*(n-1);
else {
ans[u] += 1ll*(n-sum-1)*(sum+1)+1ll*(n-1);
}
}
int main(){
cin >> n >> m;
for(int i = 1; i <= m; i++) {
ll u, v;
cin >> u >> v;
add_edge(u, v);
add_edge(v, u);
}
tarjan(1, 0);
for(int i = 1; i <= n; i++) {
cout << ans[i] << "\n";
}
return 0;
}