题目描述

Farmer John注意到他的奶牛们如果被关得太紧就容易吵架，所以他想开放一些新的牛棚来分散她们。

每当FJ建造一个新牛棚的时候，他会将这个牛棚用至多一条双向道路与一个现有的牛棚连接起来。为了确保他的奶牛们足够分散，他有时想要确定从某个特定的牛棚出发，到它能够到达的最远的牛棚的距离（两个牛棚之间的距离等于从一个牛棚出发到另一个之间必须经过的道路条数）。

FJ总共会给出次请求，每个请求都是“建造”和“距离”之一。对于一个建造请求，FJ建造一个牛棚，并将其与至多一个现有的牛棚连接起来。对于一个距离请求，FJ向你询问从某个特定的牛棚通过一些道路到离它最远的牛棚的距离。保证询问的牛棚已经被建造。请帮助FJ响应所有的请求。

输入描述:

第一行包含一个整数。以下行，每行包含一个请求。每个请求的格式都是或是，分别告诉你建造一个牛棚并与牛棚连接，或是根据定义求从牛棚出发最远的距离。如果，则新的牛棚不会与其他牛棚连接。否则，是一个已经建造的牛棚的编号。牛棚编号从1开始，所以第一个被建造的谷仓是1号谷仓，第二个是2号谷仓，以此类推。

输出描述:

对于每个距离请求输出一行。注意一个没有连接到其他牛棚的牛棚的最远距离为0.

示例1

输入
7
B -1
Q 1
B 1
B 2
Q 3
B 2
Q 2
输出
0
2
1
说明
输入样例对应下面的牛棚网：

(1)
\
(2)---(4)
/
(3)

对于请求1，我们建造牛棚1。对于请求2，我们询问从1出发到最远连接的牛棚的距离。由于牛棚1没有与其他牛棚连接，所以回答是0。对于请求3，我们建造牛棚2并将其与牛棚1连接。对于请求4，我们建造牛棚3并将其与牛棚2连接。对于请求5，我们询问从3出发到最远连接的牛棚的距离。在这时，最远的是牛棚1，距离为2单位。对于请求6，我们建造牛棚4并将其与牛棚2连接。对于请求7，我们询问从2出发到最远连接的牛棚的距离。所有其他三个牛棚1，3，4都与2相距相同的距离1，所以这就是我们的回答。

解答

初始图上无点

接下来有个操作

操作，有一个参数，表示新增加一个节点（编号为现在图中节点个数），连向（双向边）编号为的节点，如果则不连边

操作，有一个参数，询问编号为的节点到图中相对于是最远点的距离（或者说，将作为根，询问深度最大的节点的深度）

说道连边，我就想起某（其实本来是想着玄学做法的2333）

我们可以注意到，如果每个操作都去修改全部节点的话，操作，操作

如果不去修改，那每次查询要遍历全图，操作，操作

我当时想到这个的时候，我还在想能不能写树分块。。。但是显然不好写啊（而且不一定真的能写）

所以我们还是要讨论正解做法

伟大的学长曾经说过："是维护直径啊","题"

于是我们引入一条重要的结论，树的直径的端点之一一定是树上任意一个点的最远点之一

读者自证不难（我觉得我说出来的太拗口了）

然后我发现我不会

不过我们思索一下，我们究竟需要维护什么？

维护点之间的距离，插入叶子节点

如果学过树链剖分或者做过其他题，应该知道其实是维护两个点的

支持动态插入的算法，其实倍增就行了

倍增的码风是受了洛谷第一篇题解感染的 

int LCA(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    while(dep[x]>dep[y])
    {
        x=fa[x][lg[dep[x]-dep[y]]-1];
    }
    if(x==y)return x;
    for(int i=lg[dep[x]]-1;i>=0;i--)
    {
        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
    }
    return fa[x][0];
}
int range(int x,int y)
{
    return dep[x]+dep[y]-2*dep[LCA(x,y)];
}

然后对于每个，显然答案为∗树的直径左端点∗/),∗树的直径右端点∗/))

问题就是如何动态修改树的直径

对于每个操作，树的直径只有三种情况

一，不变，

二，左端点变为

三，右端点变为

其实我们只需要比较刚刚这三种情况的树的直径的大小就好了

然后由于有不连边操作，我们多开一个数组记录这个点的在哪颗树上 

void link(int x)
{
    ++idx;//点的编号
    if(x==-1)
    {
        g[idx]=idx;
        fa[idx][0]=idx;
        l[idx]=r[idx]=idx;
        return;
    }
    fa[idx][0]=x;
    dep[idx]=dep[x]+1;
    g[idx]=g[x];
    for(int i=1;(1<<i)<=dep[idx];i++)
    {
        fa[idx][i]=fa[fa[idx][i-1]][i-1];
    }
    int dis1=range(l[g[idx]],r[g[idx]]),dis2=range(idx,l[g[idx]]),dis3=range(idx,r[g[idx]]);
    if(dis2>dis1&&dis2>=dis3)r[g[idx]]=idx;
    if(dis3>dis1&&dis3>dis2)l[g[idx]]=idx;
}
请注意最后的判断语句不要写成和或者是和（想一想为什么），我觉得其实就我这个傻子这里还写挂了一次
#include<iostream>
#include<cmath>
using namespace std;
int n,idx;
int l[100001],r[100001],fa[100001][37],dep[100001],g[100001],lg[100001];
int LCA(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    while(dep[x]>dep[y])
    {
        x=fa[x][lg[dep[x]-dep[y]]-1];
    }
    if(x==y)return x;
    for(int i=lg[dep[x]]-1;i>=0;i--)
    {
        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
    }
    return fa[x][0];
}
int range(int x,int y)
{
    return dep[x]+dep[y]-2*dep[LCA(x,y)];
}
void link(int x)
{
    ++idx;
    if(x==-1)
    {
        g[idx]=idx;
        fa[idx][0]=idx;
        l[idx]=r[idx]=idx;
        return;
    }
    fa[idx][0]=x;
    dep[idx]=dep[x]+1;
    g[idx]=g[x];
    for(int i=1;(1<<i)<=dep[idx];i++)
    {
        fa[idx][i]=fa[fa[idx][i-1]][i-1];
    }
    int dis1=range(l[g[idx]],r[g[idx]]),dis2=range(idx,l[g[idx]]),dis3=range(idx,r[g[idx]]);
    if(dis2>dis1&&dis2>=dis3)r[g[idx]]=idx;
    if(dis3>dis1&&dis3>dis2)l[g[idx]]=idx;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        lg[i]=lg[i-1]+((1<<lg[i-1])==i);
    }
    for(int i=1;i<=n;i++)
    {
        char opt;
        int x;
        cin>>opt>>x;
        if(opt=='B')
        {
            link(x);
        }
        else
        {
            cout<<max(range(l[g[x]],x),range(x,r[g[x]]))<<endl;
        }
    }
    return 0;
}

来源：千柒/Kan_kiz