科学家在观测一棵大树, 这棵树在不断地生长, 科学家给这棵树的每个节点编了号. 开始的时候, 这棵树很小只有
4 个节点, 一号点为根, 其他三个节点挂在上面. 在接下来的 M 次观察中, 科学家每次都能看见这棵树从叶子处长出
新的两个节点来. 如果当前这棵树有 N 个节点, 那么这棵树的新的两个节点的编号分别为 N+1,N+2. 科学家记录下
了这棵树生长的过程, 需要你帮着计算这棵树实时的直径. 树的直径就是这棵树最远的两个节点的距离.
Input
第一行一个整数 M, 代表观察的次数.
接下来 M 行, 每行一个整数 x,
代表这棵树的编号为 x 的节点下面又长了两个叶子节点. 保证每次生长的节点都是叶子节点.
- N<=100000.
- Output
M 行, 每次生长后这棵树的直径.
- Sample Input
- 5
- 2
- 3
- 4
- 8
- 5
- Sample Output
- 3
- 4
- 4
- 5
- 6
- Sol:
树的直径有一个性质.
现在有两棵树, 如果把它们随意连一条边, 会变成一棵树, 新树的直径的端点一定是之前两棵树的直径的共 4 个端点的两个.
所以这题搞个倍增就可以在线了.
- #include<cstdio>
- #include<algorithm>
- #define fo(i, x, y) for(int i = x; i <= y; i ++)
- #define fd(i, x, y) for(int i = x; i>= y; i --)
- #define max(a, b) ((a)> (b) ? (a) : (b))
- using namespace std;
- const int N = 500000;
- int n, a[N], tot;
- int son[N][2], dep[N];
- int f[17][N], ans;
- int lca(int x, int y) {
- if(dep[x] <dep[y]) swap(x, y);
- fd(i, 16, 0) if(dep[f[i][x]]>= dep[y]) x = f[i][x];
- if(x == y) return x;
- fd(i, 16, 0) if(f[i][x] != f[i][y]) x = f[i][x], y = f[i][y];
- return f[0][x];
- }
- int dis(int x, int y) {
- int lc = lca(x, y);
- return dep[x] + dep[y] - 2 * dep[lc];
- }
- int main() {
- scanf("%d", &n);
- tot = 4;
- dep[1] = 1; dep[2] = dep[3] = dep[4] = 2;
- f[0][2] = f[0][3] = f[0][4] = 1;
- int p = 2, q = 4;
- fo(i, 1, n) {
- scanf("%d", &a[i]);
- son[a[i]][0] = ++ tot;
- son[a[i]][1] = ++ tot;
- dep[tot - 1] = dep[tot] = dep[a[i]] + 1;
- f[0][tot - 1] = f[0][tot] = a[i];
- fo(j, 1, 16)
- f[j][tot - 1] = f[j - 1][f[j - 1][tot - 1]],
- f[j][tot] = f[j - 1][f[j - 1][tot]];
- if(dis(p, tot) < dis(q, tot)) swap(p, q);
- if(dis(p, q) < dis(p, tot)) q = tot;
- ans = max(ans, dis(p, q));
- printf("%d\n", ans);
- }
- }
来源: http://www.bubuko.com/infodetail-3281596.html