被部分分误导了。/fn
也要考虑比赛时碰到这种情况怎么办，”回撤“思路的能力要提升，不能拘泥于当前想的方向中。
正解思路比较直接。
考虑从一个点开始拓展时，记 ，然后把包含 的 的一个连通块拓展了，然后将
置为该连通块的点权和，然后继续拓展下去。
容易发现拓展两次之后
的值就会翻倍。所以这样的拓展只有 次。
每次拓展时，我们需要查询包含
的，点权
的一个连通块的信息。使用 kruskal 重构树 + 倍增即可。单次查询是 的。
所以本题就做完了，时间复杂度 。（其中
为值域）
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
| #include <bits/stdc++.h>
using namespace std;
#define FI first
#define SE second
#define mkp make_pair
const int N = 4e5 + 5,Lg = 20;
typedef long long ll;
int n,m,s[N];
vector<int> G[N];
struct Edge {
int u,v,w;
Edge(){}
bool operator < (const Edge &rhs) const { return w < rhs.w;}
} e[N];
int val[N],anc[Lg][N];
ll wsze[N];
int ufs[N];
int find(int x) { return ufs[x] == x ? x : ufs[x] = find(ufs[x]);}
int main() {
cin >> n >> m;
for(int i = 1;i <= n;i++) cin >> s[i],wsze[i] = s[i];
for(int i = 1;i <= m;i++)
cin >> e[i].u >> e[i].v,e[i].w = max(s[e[i].u],s[e[i].v]);
sort(e + 1,e + m + 1);
for(int i = 1;i <= n + n;i++) ufs[i] = i;
int tot = n;
for(int i = 1;i <= m;i++)
if(find(e[i].u) != find(e[i].v)) {
int p = ++tot,lc = find(e[i].u),rc = find(e[i].v);
val[p] = e[i].w;ufs[lc] = ufs[rc] = p;
anc[0][lc] = anc[0][rc] = p;wsze[p] = wsze[lc] + wsze[rc];
}
for(int j = 1;j < Lg;j++)
for(int i = 1;i <= tot;i++) anc[j][i] = anc[j - 1][anc[j - 1][i]];
for(int i = 1;i <= n;i++) {
ll now = s[i];
int x = i;
while(true) {
for(int j = Lg - 1;j >= 0;j--)
if(anc[j][x] && val[anc[j][x]] <= now) x = anc[j][x];
if(wsze[x] == now) break;
now = wsze[x];
}
if(!anc[0][x]) putchar('1');
else putchar('0');
}
return 0;
}
|