[生成树 + 并查集] Codechef October Challenge 2017 .Lucky Edge

考虑枚举枚举左端点 \(L\) ,不断加边,把边双缩起来,当一条边第一次缩掉时加上贡献。

直接 \(LCT\) 肯定 \(T\) 。我们可以先按顺序从 \(L\)\(m\) 构建出底树。加边时在这颗树上并查集合并即可。

这样复杂度就乘了一个并查集的复杂度,卡卡常就能过了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int getint(){
char ch=gc(); int res=0,ff=1;
while(!isdigit(ch)) ch=='-'?ff=-1:0, ch=gc();
while(isdigit(ch)) res=(res<<3)+(res<<1)+ch-'0', ch=gc();
return res*ff;
}
using namespace std;
const int maxn=10005,maxe=maxn*2;
struct Edge{
int x,y;
Edge(int t1=0,int t2=0){x=t1;y=t2;}
} Es[maxn];
int n,m;
int fir[maxn],nxt[maxe],son[maxe],eid[maxe],tot;
void add(int x,int y,int z){
son[++tot]=y; eid[tot]=z; nxt[tot]=fir[x]; fir[x]=tot;
}
int fa[maxn],dpt[maxn];
int getfa(int x){ return fa[x]==x?x:fa[x]=getfa(fa[x]); }
void merge(int x,int y){
x=getfa(x); y=getfa(y);
if(dpt[x]==dpt[y]) fa[x]=y, dpt[y]++;
else if(dpt[x]<dpt[y]) fa[x]=y; else fa[y]=x;
}
int b[maxn];
inline int FindID(int x){
return lower_bound(b+1,b+1+n,x)-b;
}
int pre[maxn],pre_e[maxn],dep[maxn];
int used[maxn],clk;
void dfs(int x){
used[x]=clk;
for(int j=fir[x];j;j=nxt[j])
if(son[j]!=pre[x]){
pre[son[j]]=x; pre_e[son[j]]=eid[j];
dep[son[j]]=dep[x]+1; dfs(son[j]);
}
}
int ans[maxn],v[maxn];
int _test;
int main(){
freopen("LKYEDGE.in","r",stdin);
freopen("LKYEDGE.out","w",stdout);
_test=getint();
while(_test--){
m=getint();
n=0; for(int i=1;i<=m;i++) ans[i]=0;
for(int i=1;i<=m;i++){
b[++n]=Es[i].x=getint(), b[++n]=Es[i].y=getint();
}
sort(b+1,b+1+n); n=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=m;i++) Es[i].x=FindID(Es[i].x), Es[i].y=FindID(Es[i].y);
for(int L=1;L<=m;L++){
for(int i=1;i<=n;i++) fa[i]=i, dpt[i]=1, fir[i]=0; tot=1;
clk++; v[0]=0;
for(int i=L;i<=m;i++){
if(getfa(Es[i].x)==getfa(Es[i].y)){ v[++v[0]]=i; continue; }
add(Es[i].x,Es[i].y,i); add(Es[i].y,Es[i].x,i);
merge(Es[i].x,Es[i].y);
}
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=v[0];i++){
int x=getfa(Es[v[i]].x),y=getfa(Es[v[i]].y);
if(used[x]!=clk) pre[x]=dep[x]=pre_e[x]=0, dfs(x);
while(x!=y){
if(dep[x]<dep[y]) swap(x,y);
fa[x]=pre[x]; ans[pre_e[x]]+=m-v[i]+1;
x=getfa(x);
}
ans[v[i]]+=m-v[i]+1;
}
}
for(int i=1;i<=m;i++) printf("%d ",ans[i]); printf("\n");
}
return 0;
}