边分治

边分治用来解决一些点分治中一些解决不了的问题。

比如说点分治时有很多棵子树,合并这些信息时不能保证时间复杂度。

而边分治时最多只会有两棵子树,就可以很好地解决问题。

算法与点分治大致相同,就是找到一条边使得删去这条边后最大的那棵子树的大小最小。

但这个算法在菊花图时时间复杂度会退化成$O(n^2)$,因此需要将原树转换为一棵二叉树,这样每个点度数最多为$3$,分治后子树大小最多为原树的$\frac{2}{3}$,就不会出现刚刚那样的问题了。

但边分治还有一个限制条件,那就是后来加进去的边对答案不会产生影响

我的多叉树转二叉树的代码,(显然最后的点数nn最多只有$2n$):

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
void dfs1(int u, int father)
{
for (int i = head[u]; i; i = nextx[i])
{
int v = vet[i];
if (v != father)
{
dfs1(v, u);
vec[u].push_back(v);
}
}
}

int main()
{
dfs1(1, 0);

int nn = n;
edgenum = 1;
memset(head, 0, sizeof(head));
for (int i = 1; i <= n; i++)
{
if ((int)vec[i].size() < 2)
{
for (int j = 0; j < (int)vec[i].size(); j++)
{
add(i, vec[i][j], );
add(vec[i][j], i, );
}
}
else
{
int pre = i;
for (int j = 0; j < (int)vec[i].size() - 2; j++)
{
add(pre, vec[i][j], );
add(vec[i][j], pre, );
nn++;
x[nn] = x[i];
add(pre, nn, );
add(nn, pre, );
pre = nn;
}
add(pre, vec[i][vec[i].size() - 2], );
add(vec[i][vec[i].size() - 2], pre, );
add(pre, vec[i][vec[i].size() - 1], );
add(vec[i][vec[i].size() - 1], pre, );
}
}
}

当然可以更简单粗暴一些,代价就是点数会稍微多一点点,但还是不会超过$2n$:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main()
{
dfs1(1, 0);

int nn = n;
edgenum = 1;
memset(head, 0, sizeof(head));
for (int u = 1; u <= n; u++)
{
int pre = u;
for (int i = 0; i < (int)vec[u].size(); i++)
{
add(pre, vec[u][i], );
add(vec[u][i], pre, );
nn++;
add(pre, nn, );
add(nn, pre, );
pre = nn;
}
}
}

其他的部分和点分治差不多。

这里是找根的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void getroot(int u, int father, int S)
{
size[u] = 1;
for (int i = head[u]; i; i = nextx[i])
{
int v = vet[i];
if (v != father && ! vis[i])
{
getroot(v, u, S);
f[i >> 1] = std::max(size[v], S - size[v]);
if (f[i >> 1] < f[root >> 1])
{
root = i;
}
size[u] += size[v];
}
}
}

分治的大致框架:

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
void dfs(int u, int father, int cas, )
{
size[u] = 1;
for (int i = head[u]; i; i = nextx[i])
{
int v = vet[i];
if (v != father && ! vis[i])
{
dfs(v, u, cas, );
size[u] += size[v];
}
}
//
}

void solve(int rt, int father, int S)
{
if (! rt)
{
return;
}
vis[rt] = vis[rt ^ 1] = 1;
for (int i = 0; i < 2; i++)
{
dfs(vet[rt ^ i], 0, i, );
}
//solve
for (int i = 0; i < 2; i++)
{
root = 0;
int ss = size[vet[rt ^ i]];
getroot(vet[rt ^ i], 0, ss);
solve(root, 0, ss);
}
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×