可能是因为你可能合并之后的果子数仍然小于下一堆
by 司徒stuart @ 2016-10-28 21:32:06
你只考虑了第一遍走的时候的小堆和大堆，但在你执行完合并操作之后，是要对堆进行调整和优化的！
by wsyzz @ 2016-11-05 07:15:11
```cpp
#include<iostream>
#include<cmath>
using namespace std;
int n, m, q, anc[100][32], he[100], deep[100], cnt;
struct mine
{
int to,ne;
} ed[100];
void add(int x, int y)
{
cnt++;
ed[cnt].to = y;
ed[cnt].ne = he[x];
he[x] = cnt;
}
void dfs(int now, int fr)
{
for (int tmp = he[now]; tmp != 0; tmp = ed[tmp].ne)
{
if (ed[tmp].to == fr) continue;
deep[ed[tmp].to] = deep[now] + 1;
dfs(ed[tmp].to, now);
anc[ed[tmp].to][0] = now;
}
}
void ready()
{
for (int i = 1; (1 << i) <= n; i++)
for (int j = 1; j <= n; j++)
anc[j][i] = anc[anc[j][i - 1]][i - 1];
}
int getlca(int x, int y)
{
if (deep[x] < deep[y]) swap(x, y);
int maxlogn = floor(log(n) / log(2));
for (int i = maxlogn; i >= 0; i--)
if (deep[x] - (1 << i) >= deep[y])
x = anc[x][i];
if (x == y) return x;
for (int i = maxlogn; i >= 0; i--)
if (anc[x][i] != anc[y][i])
{
x = anc[x][i];
y = anc[y][i];
}
return anc[x][0];
}
int main()
{
freopen("lca.in", "r", stdin);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
dfs(1,1);
ready();
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
{
cout << i << " " << j << " " << getlca(i, j) << endl;
}
return 0;
}
```
by 王中立 @ 2017-01-15 10:53:28
```cpp
**#include<iostream>**
**#include<cmath>
using namespace std;
int n, m, q, anc[100][32], he[100], deep[100], cnt;
struct mine
{
int to,ne;
} ed[100];
void add(int x, int y)
{
cnt++;
ed[cnt].to = y;
ed[cnt].ne = he[x];
he[x] = cnt;
}
void dfs(int now, int fr)
{
for (int tmp = he[now]; tmp != 0; tmp = ed[tmp].ne)
{
if (ed[tmp].to == fr) continue;
deep[ed[tmp].to] = deep[now] + 1;
dfs(ed[tmp].to, now);
anc[ed[tmp].to][0] = now;
}
}
void ready()
{
for (int i = 1; (1 << i) <= n; i++)
for (int j = 1; j <= n; j++)
anc[j][i] = anc[anc[j][i - 1]][i - 1];
}
int getlca(int x, int y)
{
if (deep[x] < deep[y]) swap(x, y);
int maxlogn = floor(log(n) / log(2));
for (int i = maxlogn; i >= 0; i--)
if (deep[x] - (1 << i) >= deep[y])
x = anc[x][i];
if (x == y) return x;
for (int i = maxlogn; i >= 0; i--)
if (anc[x][i] != anc[y][i])
{
x = anc[x][i];
y = anc[y][i];
}
return anc[x][0];
}
int main()
{
freopen("lca.in", "r", stdin);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
dfs(1,1);
ready();
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
{
cout << i << " " << j << " " << getlca(i, j) << endl;
}
return 0;
}**
```
by 王中立 @ 2017-01-15 10:54:20