题目概述

有一棵黑白两种颜色的树，两种操作：1.修改一个节点的颜色。2.询问最远的黑点之间的距离。

解题报告

如果没有修改的话就是裸的点分治，但是有修改的话就凉了……这里要用到点分树，可以实现动态点分治。

点分树把原树按照每次选重心的方法建成一棵新树，根据点分治的性质可以发现这棵树深度是 $O(log_2n)$ 的，于是我们可以暴力维护每个节点在原树中的信息。

比如这道题，建出点分树之后我们对于每个节点维护一个数据结构记录下该节点原树子树中所有节点到该节点点分树父亲的原树距离，再维护一个数据结构表示该节点点分树儿子的原树子树中到该节点原树距离的所有最大值，然后每次选出最大和次大，再放进一个全局数据结构中维护最大值。

大概是这样（ $fa_i$ 表示点分树中的父亲）：

• $A_i$ ：存下了 $i$ 原树子树中到 $fa_i$ 的所有原树距离。
• $B_i$ ：存下了 $i$ 所有点分树儿子的 $max\{A_i\}$ 。
• $Ans$ ：存下了所有 $max\{B_i\}+secondmax\{B_i\}$ ，$max\{Ans\}$ 就是答案。

在修改的时候，因为深度 $O(log_2n)$ 所以直接暴力往上修改就行啦。

我直接用multiset维护了……不过好像可以两个堆来实现删除操作。

示例程序

#include<set>
#include<queue>
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn=100000,Log=17;

int n,te,S,si[maxn+5],MAX[maxn+5],ro,fa[maxn+5];bool vis[maxn+5];
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5];
int dep[maxn+5],ST[maxn+5][Log+5];bool us[maxn+5];
multiset<int> A[maxn+5],B[maxn+5],ans;multiset<int>::iterator it;

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
void getST(int x,int pre=0){
    dep[x]=dep[pre]+1;ST[x][0]=pre;for (int j=1;j<=Log;j++) ST[x][j]=ST[ST[x][j-1]][j-1];
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) getST(son[j],x);
}
void getro(int x,int pre=0){ //获取重心
    for (int j=(si[x]=1,MAX[x]=0,lnk[x]),u;j;j=nxt[j])
        if (!vis[u=son[j]]&&u!=pre) getro(u,x),si[x]+=si[u],MAX[x]=max(MAX[x],si[u]);
    MAX[x]=max(MAX[x],S-si[x]);if (!ro||MAX[x]<MAX[ro]) ro=x;
}
inline int LCA(int x,int y){
    if (dep[x]<dep[y]) swap(x,y);for (int j=Log;~j&&dep[x]>dep[y];j--) if (dep[ST[x][j]]>=dep[y]) x=ST[x][j];
    if (x==y) return x;for (int j=Log;~j;j--) if (ST[x][j]!=ST[y][j]) x=ST[x][j],y=ST[y][j];return ST[x][0];
}
#define Dis(x,y) (dep[x]+dep[y]-(dep[LCA(x,y)]<<1))
void Join(int ro,int x,int pre=0){ //暴力获取A
    A[ro].insert(-Dis(x,fa[ro]));
    for (int j=lnk[x];j;j=nxt[j])
        if (!vis[son[j]]&&son[j]!=pre) Join(ro,son[j],x);
}
inline void Insert(int x){ //把B[x]的贡献加入Ans
    if (B[x].size()>1) it=B[x].begin(),it++,ans.insert(*B[x].begin()+*it);
    else if (B[x].size()==1&&!us[x]) ans.insert(*B[x].begin());
}
inline void Delete(int x){ //从Ans中删除B[x]的贡献
    if (B[x].size()>1) it=B[x].begin(),it++,ans.erase(ans.find(*B[x].begin()+*it));
    else if (B[x].size()==1&&!us[x]) ans.erase(ans.find(*B[x].begin()));
}
void Dfs(int x,int pre=0){ //点分树构造
    vis[x]=true;fa[x]=pre;if (pre) Join(x,x);int sum=S;
    for (int j=lnk[x],u;j;j=nxt[j])
        if (!vis[u=son[j]]){
            S=si[x]>si[u]?si[u]:sum-si[x];ro=0;getro(u,x);
            int now=ro;Dfs(ro,x);B[x].insert(*A[now].begin());
        }
}
inline char getupr() {char ch=readc();while (!isupper(ch)) ch=readc();return ch;}
inline void Update(int x){ //修改操作
    Delete(x);us[x]^=1;Insert(x);
    for (int i=x;fa[i];i=fa[i]){
        Delete(fa[i]);if (A[i].size()) B[fa[i]].erase(B[fa[i]].find(*A[i].begin()));
        if (us[x]) A[i].erase(A[i].find(-Dis(x,fa[i]))); else A[i].insert(-Dis(x,fa[i]));
        if (A[i].size()) B[fa[i]].insert(*A[i].begin());Insert(fa[i]);
    }
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);for (int i=1,x,y;i<n;i++) readi(x),readi(y),Add(x,y),Add(y,x);
    getST(1);S=n;ro=0;getro(1);Dfs(ro);for (int i=1;i<=n;i++) Insert(i);
    for (int x=readi(te);te;te--){
        if (getupr()=='C') readi(x),Update(x);
        else printf("%d\n",-*ans.begin());
    }return 0;
}