Description
众所周知，小 naive 有一张 n 个点，m 条边的带权无向图。第 i 个点的颜色为 ci。d(s, t)表示从点 s 到点 t 的权值最小的路径的权值，一条路径的权值定义为路径上权值最大的边的权值。 求所有满足 u < v, |cu − cv| ≥ L 的点对 (u, v) 的 d(u, v) 之和。
Solution
最后5秒没交上去。。
第一个条件没什么用，只是为了防止算重，我们可以不管它。 显然这样的边会在最小生成树上。我们从小到大枚举边，显然一条边会连通两个连通块 考虑算这条边的贡献，我们枚举size较小的子树中的节点，查询另一子树中给定区间内c的数量 于是我们可以每个联通块开一棵线段树，每次合并连通块就线段树合并，每次线段树区间查询
算一下复杂度。由于每个连通块合并一次后size至少变为2倍，因此只会合并log次，每个元素只会被插入log^2次。线段树合并的复杂度我不会算，但是可知和元素个数有关，实测随机数据表现优良。 空间按理说应该开nlog^2的，但是出题人并没有卡这个东西。。。 感觉这样就是在倒着边分治啊
嗯，这很noip模拟
Code
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
typedef long long LL
;
const int N
=200005;
const int E
=500005;
struct edge
{int x
,y
,w
;} h
[N
],g
[E
];
struct treeNode
{int l
,r
,sum
;} t
[N
*51];
struct data
{
int fi
,se
;
bool operator <(data b
) const {
return (fi
!=b
.fi
)?(fi
<b
.fi
):(se
<b
.se
);
}
} ;
std
:: vector
<data
> vec
[N
];
int c
[N
],size
[N
],root
[N
],fa
[N
];
int lim
,tot
,n
;
int read() {
int x
=0,v
=1; char ch
=getchar();
for (;ch
<'0'||ch
>'9';v
=(ch
=='-')?(-1):(v
),ch
=getchar());
for (;ch
<='9'&&ch
>='0';x
=x
*10+ch
-'0',ch
=getchar());
return x
*v
;
}
int query(int now
,int tl
,int tr
,int l
,int r
) {
if (r
<l
) return 0;
if (tl
>=l
&&tr
<=r
) return t
[now
].sum
;
int mid
=(tl
+tr
)>>1;
int qx
=query(t
[now
].l
,tl
,mid
,l
,std
:: min(r
,mid
));
int qy
=query(t
[now
].r
,mid
+1,tr
,std
:: max(mid
+1,l
),r
);
return qx
+qy
;
}
void modify(int &now
,int tl
,int tr
,int x
,int v
) {
if (!now
) now
=++tot
; t
[now
].sum
+=v
;
if (tl
==tr
) return ;
int mid
=(tl
+tr
)>>1;
if (x
<=mid
) modify(t
[now
].l
,tl
,mid
,x
,v
);
else modify(t
[now
].r
,mid
+1,tr
,x
,v
);
}
int merge(int x
,int y
,int tl
,int tr
) {
if (!x
||!y
) return x
+y
;
int mid
=(tl
+tr
)>>1;
t
[x
].l
=merge(t
[x
].l
,t
[y
].l
,tl
,mid
);
t
[x
].r
=merge(t
[x
].r
,t
[y
].r
,mid
+1,tr
);
t
[x
].sum
+=t
[y
].sum
;
return x
;
}
int ask(int root
,int x
,int L
) {
return query(root
,0,lim
,std
:: max(0,x
-L
+1),std
:: min(x
+L
-1,lim
));
}
int find(int x
) {
return !fa
[x
]?x
:(fa
[x
]=find(fa
[x
]));
}
bool cmp(edge a
,edge b
) {
return a
.w
<b
.w
;
}
int main(void) {
freopen("data.in","r",stdin);
n
=read(); int m
=read(),L
=read(),cnt
=0;
rep(i
,1,n
) c
[i
]=read(),lim
=std
:: max(lim
,c
[i
]);
rep(i
,1,m
) {
int x
=read(),y
=read(),w
=read();
g
[i
].x
=x
,g
[i
].y
=y
,g
[i
].w
=w
;
}
std
:: sort(g
+1,g
+m
+1,cmp
);
rep(i
,1,m
) {
if (find(g
[i
].x
)!=find(g
[i
].y
)) {
fa
[find(g
[i
].x
)]=find(g
[i
].y
);
h
[++cnt
]=g
[i
];
}
} tot
=n
;
rep(i
,1,n
) {
fa
[i
]=0,size
[i
]=1;
vec
[i
].push_back((data
) {i
,c
[i
]});
root
[i
]=i
;
modify(root
[i
],0,lim
,c
[i
],1);
}
LL ans
=0;
rep(ti
,1,cnt
) {
int x
=h
[ti
].x
,y
=h
[ti
].y
;
int fx
=find(x
),fy
=find(y
);
if (size
[fx
]>size
[fy
]) {
std
:: swap(fx
,fy
);
std
:: swap(x
,y
);
}
int szefx
=vec
[fx
].size(),szefy
=vec
[fy
].size();
for (int i
=0,j
=0;i
<szefx
;++i
) {
LL
tmp(szefy
-ask(root
[fy
],vec
[fx
][i
].se
,L
));
ans
+=1LL*h
[ti
].w
*tmp
;
}
for (int i
=0;i
<szefx
;++i
) vec
[fy
].push_back(vec
[fx
][i
]);
root
[fy
]=merge(root
[fy
],root
[fx
],0,lim
);
fa
[fx
]=fy
; size
[fy
]+=size
[fx
];
}
printf("%lld\n", ans
);
return 0;
}
