![洛谷 P2056 [ZJOI2007]捉迷藏 || bzoj 1095: [ZJOI2007]Hide 捉迷藏 || 洛谷 P4115 Qtree4 || SP2666 QTREE4 - Query on a tree IV](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1 "洛谷 P2056 [ZJOI2007]捉迷藏 || bzoj 1095: [ZJOI2007]Hide 捉迷藏 || 洛谷 P4115 Qtree4 || SP2666 QTREE4 - Query on a tree IV")
意识到一点：在进行点分治时，每一个点都会作为某一级重心出现，且任意一点只作为重心恰好一次。因此原树上任意一个节点都会出现在点分树上，且是恰好一次
https://www.cnblogs.com/zzqsblog/p/6393023.html
对比http://www.cnblogs.com/hehe54321/p/8570320.html的普通点分程序，"到分治树上这个点父亲的距离"相当于solve(u)时各个cal函数计算出的值对ans的总贡献，只不过改成了动态维护这个值。
普通点分由"分治树上这个点父亲"来计算"这个点"的贡献，需要容斥解决（当然这道题维护所求值不需要容斥）；这道题则维护某个重心管辖的连通块中各个点到该重心的上层重心的距离，这样修改某个点的贡献时，就可以修改该点到最上层重心的各个点维护的关于该点的信息。
不能维护各个点到该重心的距离，一定要维护到上层重心的距离，否则无法区分开各个子树。
（失败代码：
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
struct E
{
int to,nxt;
}e[];
int f1[],ne;
int ff[],n,sum,fx[],dep[],sz[];
int eu[],pos[],dpx[],st[][],log2x[];
int root;
bool fl[],vis[];
multiset<int> s[],s2;
//s[i]:i点管辖的连通块各个点到i点的距离
//s2:各个s的最大值
int getdis(int x,int y)
{
int l=pos[x],r=pos[y];if(l>r) swap(l,r);
int k=log2x[r-l+],t=dpx[pos[st[l][k]]]>dpx[pos[st[r-(<<k)+][k]]]?st[r-(<<k)+][k]:st[l][k];
return dpx[pos[x]]+dpx[pos[y]]-*dpx[pos[t]];
}
void getroot(int u,int fa)
{
sz[u]=;fx[u]=;
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to]&&e[k].to!=fa)
{
getroot(e[k].to,u);
sz[u]+=sz[e[k].to];
fx[u]=max(fx[u],sz[e[k].to]);
}
fx[u]=max(fx[u],sum-sz[u]);
if(fx[u]<fx[root]) root=u;
}
void getsz(int u,int fa)
{
sz[u]=;
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to]&&e[k].to!=fa)
{
getsz(e[k].to,u);
sz[u]+=sz[e[k].to];
}
}
void getdeep(int u,int fa)
{
s[root].insert(dep[u]);
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to]&&e[k].to!=fa)
{
dep[e[k].to]=dep[u]+;
getdeep(e[k].to,u);
}
}
char tmp[];
int getmax2(int p)
{
if(s[p].size()<) return -0x3f3f3f3f;
auto it=s[p].rbegin();int ans=;
ans+=*it;++it;ans+=*it;
return ans;
}
void solve(int u)
{
vis[u]=;
dep[u]=;getdeep(u,);s2.insert(getmax2(u));
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to])
{
getsz(e[k].to,);sum=sz[e[k].to];
root=;getroot(e[k].to,);
ff[root]=u;
solve(root);
}
}
void dfs1(int u,int fa,int d)
{
eu[++eu[]]=u;pos[u]=eu[];dpx[eu[]]=d;
for(int k=f1[u];k;k=e[k].nxt)
if(e[k].to!=fa)
{
dfs1(e[k].to,u,d+);
eu[++eu[]]=u;
dpx[eu[]]=d;
}
} void debugxxxx(multiset<int>& s)
{
for(auto i : s) printf("%d ",i);
puts("test");
}
void change(int u)
{
int now;
for(now=u;now;now=ff[now])
{
s2.erase(s2.find(getmax2(now)));
if(!fl[u]) s[now].erase(s[now].find(getdis(u,now)));
}
fl[u]^=;
for(now=u;now;now=ff[now])
{
if(!fl[u]) s[now].insert(getdis(u,now));
s2.insert(getmax2(now));
}
}
int main()
{
fx[]=0x3f3f3f3f;
int i,j,a,b,la=,q,t;
for(i=;i<=;i++)
{
if(i>=(<<(la+))) ++la;
log2x[i]=la;
}
scanf("%d",&n);
for(i=;i<n;i++)
{
scanf("%d%d",&a,&b);
e[++ne].to=b;e[ne].nxt=f1[a];f1[a]=ne;
e[++ne].to=a;e[ne].nxt=f1[b];f1[b]=ne;
}
dfs1(,,);
for(i=;i<=eu[];i++) st[i][]=eu[i];
for(j=;(<<j)<=eu[];j++)
for(i=;i+(<<j)-<=eu[];i++)
if(dpx[pos[st[i][j-]]]>dpx[pos[st[i+(<<(j-))][j-]]])
st[i][j]=st[i+(<<(j-))][j-];
else
st[i][j]=st[i][j-];
//getdis(5,4);
sum=n;getroot(,);
solve(root);
scanf("%d",&q);
while(q--)
{
scanf("%s",tmp);
if(tmp[]=='G')
{
printf("%d\n",*s2.rbegin());
}
else if(tmp[]=='C')
{
scanf("%d",&t);
change(t);
}
}
return ;
}
)
最终代码（洛谷A不掉，好像被卡常了？）
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
struct E
{
int to,nxt;
}e[];
int f1[],ne;
int ff[],n,sum,fx[],sz[];
int eu[],pos[],dpx[],st[][],log2x[],lft[];
int root;
bool fl[],vis[];
multiset<int> s[],s2[],s3;
//s[i]:i点管辖的连通块各个点到i点上层重心的距离
//s2[i]:i点的各个下层重心的s的最大值,**再加上一个0（i点到自身距离）
//s3:各个s2的前2大值之和
int getdis(int x,int y)
{
int l=pos[x],r=pos[y];if(l>r) swap(l,r);
int k=log2x[r-l+],t=dpx[pos[st[l][k]]]>dpx[pos[st[r-lft[k]+][k]]]?st[r-lft[k]+][k]:st[l][k];
return dpx[pos[x]]+dpx[pos[y]]-*dpx[pos[t]];
}
void getroot(int u,int fa)
{
sz[u]=;fx[u]=;
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to]&&e[k].to!=fa)
{
getroot(e[k].to,u);
sz[u]+=sz[e[k].to];
fx[u]=max(fx[u],sz[e[k].to]);
}
fx[u]=max(fx[u],sum-sz[u]);
if(fx[u]<fx[root]) root=u;
}
void getsz(int u,int fa)
{
sz[u]=;
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to]&&e[k].to!=fa)
{
getsz(e[k].to,u);
sz[u]+=sz[e[k].to];
}
}
void getdeep(int u,int fa)
{
s[root].insert(getdis(u,ff[root]));
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to]&&e[k].to!=fa)
getdeep(e[k].to,u);
}
char tmp[];
int getmax2(int p)
{
if(s2[p].size()<) return -0x3f3f3f3f;
multiset<int>::reverse_iterator it=s2[p].rbegin();int ans=;
ans+=*it;++it;ans+=*it;
return ans;
}
void solve(int u)
{
vis[u]=;
s2[u].insert();
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to])
{
getsz(e[k].to,);sum=sz[e[k].to];
root=;getroot(e[k].to,);
ff[root]=u;getdeep(root,);
if(!s[root].empty()) s2[u].insert(*s[root].rbegin());
solve(root);
}
s3.insert(getmax2(u));
}
void dfs1(int u,int fa,int d)
{
eu[++eu[]]=u;pos[u]=eu[];dpx[eu[]]=d;
for(int k=f1[u];k;k=e[k].nxt)
if(e[k].to!=fa)
{
dfs1(e[k].to,u,d+);
eu[++eu[]]=u;
dpx[eu[]]=d;
}
}
//void debugxxxx(multiset<int>& s)
//{
// for(auto i : s) printf("%d ",i);
// puts("test");
//}
void change(int u)
{
int now;
s3.erase(s3.find(getmax2(u)));
if(!fl[u]) s2[u].erase(s2[u].find());
for(now=u;ff[now];now=ff[now])
{
s3.erase(s3.find(getmax2(ff[now])));
if(!s[now].empty()) s2[ff[now]].erase(s2[ff[now]].find(*s[now].rbegin()));
if(!fl[u]) s[now].erase(s[now].find(getdis(u,ff[now])));
}
fl[u]^=;
if(!fl[u]) s2[u].insert();
s3.insert(getmax2(u));
for(now=u;ff[now];now=ff[now])
{
if(!fl[u]) s[now].insert(getdis(u,ff[now]));
if(!s[now].empty()) s2[ff[now]].insert(*s[now].rbegin());
s3.insert(getmax2(ff[now]));
}
}
int num;
int main()
{
lft[]=;
fx[]=0x3f3f3f3f;
int i,j,a,b,la=,q,t;
for(i=;i<=;i++) lft[i]=(lft[i-]<<);
for(i=;i<=;i++)
{
if(i>=lft[la+]) ++la;
log2x[i]=la;
}
scanf("%d",&n);
for(i=;i<n;i++)
{
scanf("%d%d",&a,&b);
e[++ne].to=b;e[ne].nxt=f1[a];f1[a]=ne;
e[++ne].to=a;e[ne].nxt=f1[b];f1[b]=ne;
}
dfs1(,,);
for(i=;i<=eu[];i++) st[i][]=eu[i];
for(j=;(<<j)<=eu[];j++)
for(i=;i+lft[j]-<=eu[];i++)
if(dpx[pos[st[i][j-]]]>dpx[pos[st[i+lft[j-]][j-]]])
st[i][j]=st[i+lft[j-]][j-];
else
st[i][j]=st[i][j-];
sum=n;getroot(,);
solve(root);
scanf("%d",&q);
num=n;
while(q--)
{
scanf("%s",tmp);
if(tmp[]=='G')
{
if(num==) printf("-1\n");
else if(num==) printf("0\n");
else printf("%d\n",*s3.rbegin());
}
else if(tmp[]=='C')
{
scanf("%d",&t);
if(fl[t]) num++;else num--;
change(t);
}
}
return ;
}
Qtree4卡不过去...算了不卡了，反正对拍没对出错（本地n=100000,q=100000随机数据1.5秒）
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
struct E
{
int to,nxt,d;
}e[];
int f1[],ne;
int ff[],n,sum,fx[],sz[];
int eu[],pos[],dpx[],dpx2[],st[][],log2x[],lft[];
int root;
bool fl[],vis[];
multiset<int> s[],s2[],s3;
//s[i]:i点管辖的连通块各个点到i点上层重心的距离
//s2[i]:i点的各个下层重心的s的最大值,**再加上一个0（i点到自身距离）
//s3:各个s2的前2大值之和
int getdis(int x,int y)
{
int l=pos[x],r=pos[y];if(l>r) swap(l,r);
int k=log2x[r-l+],t=dpx[pos[st[l][k]]]>dpx[pos[st[r-lft[k]+][k]]]?st[r-lft[k]+][k]:st[l][k];
return dpx2[pos[x]]+dpx2[pos[y]]-*dpx2[pos[t]];
}
void getroot(int u,int fa)
{
sz[u]=;fx[u]=;
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to]&&e[k].to!=fa)
{
getroot(e[k].to,u);
sz[u]+=sz[e[k].to];
fx[u]=max(fx[u],sz[e[k].to]);
}
fx[u]=max(fx[u],sum-sz[u]);
if(fx[u]<fx[root]) root=u;
}
void getsz(int u,int fa)
{
sz[u]=;
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to]&&e[k].to!=fa)
{
getsz(e[k].to,u);
sz[u]+=sz[e[k].to];
}
}
void getdeep(int u,int fa)
{
s[root].insert(getdis(u,ff[root]));
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to]&&e[k].to!=fa)
getdeep(e[k].to,u);
}
char tmp[];
int getmax2(int p)
{
if(s2[p].size()<) return -0x3f3f3f3f;
multiset<int>::reverse_iterator it=s2[p].rbegin();int ans=;
ans+=*it;++it;ans+=*it;
return ans;
}
void solve(int u)
{
vis[u]=;
s2[u].insert();
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to])
{
getsz(e[k].to,);sum=sz[e[k].to];
root=;getroot(e[k].to,);
ff[root]=u;getdeep(root,);
if(!s[root].empty()) s2[u].insert(*s[root].rbegin());
solve(root);
}
s3.insert(getmax2(u));
}
void dfs1(int u,int fa,int d,int d2)
{
eu[++eu[]]=u;pos[u]=eu[];dpx[eu[]]=d;dpx2[eu[]]=d2;
for(int k=f1[u];k;k=e[k].nxt)
if(e[k].to!=fa)
{
dfs1(e[k].to,u,d+,d2+e[k].d);
eu[++eu[]]=u;
dpx[eu[]]=d;
dpx2[eu[]]=d2;
}
}
//void debugxxxx(multiset<int>& s)
//{
// for(auto i : s) printf("%d ",i);
// puts("test");
//}
void change(int u)
{
int now;
s3.erase(s3.find(getmax2(u)));
if(!fl[u]) s2[u].erase(s2[u].find());
for(now=u;ff[now];now=ff[now])
{
s3.erase(s3.find(getmax2(ff[now])));
if(!s[now].empty()) s2[ff[now]].erase(s2[ff[now]].find(*s[now].rbegin()));
if(!fl[u]) s[now].erase(s[now].find(getdis(u,ff[now])));
}
fl[u]^=;
if(!fl[u]) s2[u].insert();
s3.insert(getmax2(u));
for(now=u;ff[now];now=ff[now])
{
if(!fl[u]) s[now].insert(getdis(u,ff[now]));
if(!s[now].empty()) s2[ff[now]].insert(*s[now].rbegin());
s3.insert(getmax2(ff[now]));
}
}
int num;
int main()
{
lft[]=;
fx[]=0x3f3f3f3f;
int i,j,a,b,la=,q,t,c;
for(i=;i<=;i++) lft[i]=(lft[i-]<<);
for(i=;i<=;i++)
{
if(i>=lft[la+]) ++la;
log2x[i]=la;
}
scanf("%d",&n);
for(i=;i<n;i++)
{
scanf("%d%d%d",&a,&b,&c);
e[++ne].to=b;e[ne].nxt=f1[a];e[ne].d=c;f1[a]=ne;
e[++ne].to=a;e[ne].nxt=f1[b];e[ne].d=c;f1[b]=ne;
}
dfs1(,,,);
for(i=;i<=eu[];i++) st[i][]=eu[i];
for(j=;(<<j)<=eu[];j++)
for(i=;i+lft[j]-<=eu[];i++)
if(dpx[pos[st[i][j-]]]>dpx[pos[st[i+lft[j-]][j-]]])
st[i][j]=st[i+lft[j-]][j-];
else
st[i][j]=st[i][j-];
sum=n;getroot(,);
solve(root);
scanf("%d",&q);
num=n;
while(q--)
{
scanf("%s",tmp);
if(tmp[]=='A')
{
if(num==) printf("They have disappeared.\n");
else if(num==) printf("0\n");
else printf("%d\n",max(*s3.rbegin(),));
}
else if(tmp[]=='C')
{
scanf("%d",&t);
if(fl[t]) num++;else num--;
change(t);
}
}
return ;
}
数据生成器
var random = Math.random, floor = Math.floor, exit = process.exit, print = console.log;
var n = 100000, q = 100000;
console.log(n);
var fa = new Array(n+1), a, b, ta, tb, idx;
for(i=1; i<=n; i++) fa[i] = i;
function find(x) {return x===fa[x]?x:fa[x]=find(fa[x]);}
for(i=1; i<n; i++) {
do {
a = floor(random()*n) + 1;
b = floor(random()*n) + 1;
ta = find(a);tb = find(b);
}
while(ta == tb);
fa[ta] = tb;
console.log(a+" "+b+" "+(floor(random()*21)-10));
}
console.log(q);
for(i=1; i<=q; i++) {
idx = floor(random()*2);
if (idx === 1) {
console.log("A");
}
else {
console.log("C "+(floor(random()*n)+1));
}
}
另有：捉迷藏特殊做法