根号大军占领 Qtree
卡帕瓦_KAPawa · · 算法·理论
一、前言
昨天无意间看到了 QTREE3 这个题,发现我竟然还没做。感觉树剖或者倍增的做法也太平凡了,没啥写的欲望。我灵机一动,想出了一个单根做法。这也太喵了!我立马去看了 QTREE 系列的其它题,快速口糊了几个发现应该都能单根,而且题解区竟然没有一个人跟我想得一样!
那还说啥了,花了一天时间把 QTREE1 到 QTREE7 全通关了。给大家分享一下我的做法喵。
首先声明一下,SPOJ 的评测机真的奇慢无比,我 luogu 上跑
以及,以下的做法不论是时间复杂度还是常数基本上都是最劣解,大家看个乐呵就好,千万别学喵(逃。如果能学到有用的东西再好不过啦!
题目的排序方式是按照主观难度升序排序的。所有题的输入都是我约定的简写,实际输入格式请按照原题面。
二、QTREE2
1、题目链接
luogu RMJ 链接
SPOJ 链接
2、题意简述
给定一棵
1 x y:输出x 到y 的路径长度。2 x y k:输出x 到y 路径上的第k 个点。
3、思路简析
没有修改操作,儿简送。第一个操作也太简单了,直接预处理一个以
考虑维护一下第二个操作。如果我们能把一棵树像序列一样分成若干块,每一块的大小接近
这里,我们有一种很经典的分块方法:
设
根据鸽巢原理,此时选出的关键点个数一定小于等于
此时,我们把连接两个关键点的一条链叫做一个块。如下图:
为方便画图,我们假设
对于每个块,我们预处理出这个块内有几个点。对于查询操作,我们把一条路径拆成两条链,先看第
写代码的时候脑子不太清醒喵,把第一个操作也顺手写上了。看笨蛋喵。
:::success[核心代码]
ll t,n,u,v,w,k,cs,Qtot,tot;
ll dep[N],b[N],dist[N],fa[N],up[N][Lg],id[N],near[N],wt[N],W[N],sz[N];
vector<pair<ll,ll> > e[N];
string s;
inline void Clear(){
for(int i=1;i<=n;i++) b[i]=dist[i]=W[i]=sz[i]=id[i]=0,e[i].clear();
for(int i=1;i<=n;i++) for(int j=0;j<Lg;j++) up[i][j]=0;
return tot=b[0]=0,void();
}
inline void dfs1(ll u,ll f){
dep[u]=dep[f]+1,fa[u]=up[u][0]=f,b[dep[u]%B]++;
for(auto [v,w]:e[u]) if(v!=f) wt[v]=w,dist[v]=dist[u]+w,dfs1(v,u);
return;
}
inline void dfs2(ll u){
if(dep[u]%B==cs) id[u]=++tot;
near[u]=(id[u]?u:near[fa[u]]);
for(auto [v,w]:e[u]) if(v!=fa[u]) dfs2(v);
return;
}
inline void build(){
for(int i=1;i<=n;i++) if(id[i]){
W[id[i]]=sz[id[i]]=0;
ll p=near[fa[i]];
for(int j=i;j!=p;j=fa[j]) W[id[i]]+=wt[j],sz[id[i]]++;
}
return;
}
inline ll lca(ll u,ll v){
if(dep[u]<dep[v]) swap(u,v);
ll k=dep[u]-dep[v];
for(int j=Lg-1;~j;j--) if((k>>j)&1) u=up[u][j];
if(u==v) return u;
for(int j=Lg-1;~j;j--) if(up[u][j]!=up[v][j]) u=up[u][j],v=up[v][j];
return fa[u];
}
inline ll query(ll u,ll v){
ll ans=0,now=u;
if(dep[near[u]]<=dep[v]){
while(now!=v) ans+=wt[now],now=fa[now];
return ans;
}
while(!id[now]) ans+=wt[now],now=fa[now];
while(dep[near[fa[now]]]>dep[v]) ans+=W[id[now]],now=near[fa[now]];
while(now!=v) ans+=wt[now],now=fa[now];
return ans;
}
inline ll query2(ll u,ll k){
ll ans=u;
if(dep[u]-dep[near[u]]>=k){
while(k--) ans=fa[ans];
return ans;
}
while(!id[ans]) ans=fa[ans],k--;
while(dep[ans]-dep[near[fa[ans]]]<k) k-=sz[id[ans]],ans=near[fa[ans]];
while(k--) ans=fa[ans];
return ans;
}
int main(){
read(t);
while(t--){
read(n);
for(int i=1;i<n;i++) read(u),read(v),read(w),e[u].push_back({v,w}),e[v].push_back({u,w});
dfs1(1,0),cs=min_element(b,b+B)-b,dfs2(1);
for(int j=1;j<Lg;j++) for(int i=1;i<=n;i++) up[i][j]=up[up[i][j-1]][j-1];
build();
for(Qtot=1;;Qtot++){
read(s);
if(s=="DONE") break;
if(s=="DIST"){
read(u),read(v);
ll _lca=lca(u,v);
if(u==v) write(0,'\n');
else if(_lca==u) write(query(v,u),'\n');
else if(_lca==v) write(query(u,v),'\n');
else write(query(u,_lca)+query(v,_lca),'\n');
}
else{
read(u),read(v),read(k);
ll p=lca(u,v),du=dep[u]-dep[p],dv=dep[v]-dep[p];
if(k<=du+1) write(query2(u,k-1),'\n');
else write(query2(v,du+dv+1-k),'\n');
}
}
pc('\n'),Clear();
}
return 0;
}
:::
三、QTREE5
1、题目链接
luogu RMJ 链接
SPOJ 链接
2、题意简述
给定一棵
1 x:将x 的颜色反转。2 x:输出x 到最近的一个白色点的距离。
3、思路简析
单点修改一定要想想操作序列分块喵。
我们考虑操作序列分块。操作序列分块是一种套路,常见写法是设定一个阈值
对于这道题,我们把操作暂存下来,存到
对于一次查询,我们分两种情况:答案所对应的白点是确定点或是不确定点。
所有确定点的颜色一定不会发生变化。那么原来是白色的点现在也一定是白色。以所有确定白点为源,在整棵原树上做多源 BFS 即可求出每个点到距离其最近的确定白点的距离。这一部分预处理时间复杂度
因为我们只存了
加上
:::success[核心代码]
ll n,u,v,q,x[N],op[N],dep[N],fst[N],st[Lg][N<<1],dis[N],T,num;
vector<ll> e[N],tmp;
bool used[N],col[N];
queue<ll> Q;
inline ll mn(ll u,ll v){return dep[u]<dep[v]?u:v;}
inline void dfs1(ll u,ll f){
dep[u]=dep[f]+1,fst[u]=++T,st[0][T]=u;
for(auto v:e[u]) if(v!=f) dfs1(v,u),st[0][++T]=u;
return;
}
inline void init(){
for(int j=1;(1<<j)<=T;j++) for(int i=1;i+(1<<j)-1<=T;i++) st[j][i]=mn(st[j-1][i],st[j-1][i+(1<<(j-1))]);
return;
}
inline ll lca(ll u,ll v){
ll l=fst[u],r=fst[v];
if(l>r) swap(l,r);
ll k=__lg(r-l+1);
return mn(st[k][l],st[k][r-(1<<k)+1]);
}
inline void rebuild(){
for(int i=1;i<=n;i++) dis[i]=inf;
for(int i=1;i<=n;i++) if(col[i]&&!used[i]) Q.push(i),dis[i]=0;
while(!Q.empty()){
ll u=Q.front();Q.pop();
for(auto v:e[u]) if(dis[v]==inf) dis[v]=dis[u]+1,Q.push(v);
}
return;
}
inline ll query(ll u){
if(col[u]) return 0;
ll ans=dis[u];
for(auto v:tmp) if(col[v]) ans=min(ans,dep[u]+dep[v]-2*dep[lca(u,v)]);
return ans==inf?-1:ans;
}
int main(){
read(n);
for(int i=1;i<n;i++) read(u),read(v),e[u].push_back(v),e[v].push_back(u);
dfs1(1,0),init();
read(q);
for(int i=1;i<=q;i++) read(op[i]),read(x[i]);
for(int l=1;l<=q;l+=B){
ll r=min(l+B-1,q);
tmp.clear();
for(int i=l;i<=r;i++) if(!op[i]&&!used[x[i]]) used[x[i]]=true,tmp.push_back(x[i]);
rebuild();
for(int i=l;i<=r;i++){
if(!op[i]) num-=col[x[i]],col[x[i]]^=1,num+=col[x[i]];
else write(num?query(x[i]):-1,'\n');
}
for(int i=l;i<=r;i++) used[x[i]]=false;
}
return 0;
}
:::
四、QTREE3
1、题目链接
luogu 主题库链接
SPOJ 链接
2、题意简述
给定一棵
1 x:将x 的颜色翻转。2 x:输出1 到x 路径上的第一个黑色点。
3、思路简析
我们还是采用 QTREE2 的思路,按照深度模
然后,我们考虑对每个块维护一个 vector,表示这个块内所有黑色的点。按深度排好序。
对于一个查询操作,我们暴力向上跳到离它最近的关键点,顺便更新答案;再在当前节点到根节点的所有块的 vector 的第一个元素里选一个深度最小的即可。
我们发现单点修改要修改一个子树中所有关键点的 vector,时间复杂度还是不对。所以要考虑操作序列分块。
把修改操作暂存起来。每存
处理
现在只需要额外考虑所有查询时为黑色的不确定点。判断当前询问的点在不在它的子树内即可。
暴力重构是简单的,一共至多
总时间复杂度为
:::success[核心代码]
ll n,q,op,x,u,v,fa[N],id[N],dep[N],tung[N],near[N],cs,tot,dfn[N],sz[N],T;
vector<pair<ll,ll> > Dep;
vector<ll> e[N],S[N/B+10],cg;
bool col[N];
inline void dfs1(ll u,ll f){
dep[u]=dep[f]+1,tung[dep[u]%B]++,dfn[u]=++T,sz[u]=1,fa[u]=f;
for(auto v:e[u]) if(v!=f) dfs1(v,u),sz[u]+=sz[v];
return;
}
inline void dfs2(ll u){
if(dep[u]%B==cs) id[u]=++tot;
near[u]=id[u]?u:near[fa[u]];
for(auto v:e[u]) if(v!=fa[u]) dfs2(v);
return;
}
inline ll query(ll u){
ll Ans=-1,v=near[u];
for(int i=u;i!=v;i=fa[i]) if(col[i]) Ans=i;
for(int i=v;i;i=near[fa[i]]) for(auto x:S[id[i]]) if(col[x]){Ans=x;break;}
for(auto x:cg) if(col[x]&&dfn[x]<=dfn[u]&&dfn[x]+sz[x]>dfn[u]&&(Ans==-1||dep[x]<dep[Ans])) Ans=x;
return Ans;
}
inline void rebuild(){
cg.clear();
for(int i=1;i<=n;i++) if(id[i]){
ll op=near[fa[i]];
S[id[i]].clear();
for(int j=i;j!=op;j=fa[j]) if(col[j]) S[id[i]].push_back(j);
reverse(S[id[i]].begin(),S[id[i]].end());
}
return;
}
int main(){
read(n),read(q);
for(int i=1;i<n;i++) read(u),read(v),e[u].push_back(v),e[v].push_back(u);
dfs1(1,0),cs=min_element(tung,tung+B)-tung,dfs2(1);
while(q--){
read(op),read(x);
if(op==0) col[x]^=1,cg.push_back(x);
else write(query(x),'\n');
if(cg.size()>=B) rebuild();
}
return 0;
}
:::
五、QTREE1
1、题目链接
luogu RMJ 链接
luogu 主题库链接
SPOJ 链接
2、题意简述
给定一棵
1 x y:将第x 条边的边权改为y 。2 x y:输出x 到y 路径上的最大边权。
3、思路简析
首先随便选一个点当作根节点,把所有边的边权放到它的儿子节点上,当作它儿子节点的点权即可。下面都称边权为点权。
相似的,我们还是按照深度模
我们暂存
预处理时,我们对于每一块预处理出当前块内所有确定点的点权最大值。
那么对于一次查询,只需要把路径拆成两条链,分别查询两条链上确定点的点权最大值,再暴力遍历所有不确定点,更新答案即可。枚举不确定点时,只考虑在
查询链上的确定点的点权最大值和上面的做法差不多,只需要暴力遍历两端不完整的块,中间完整的块用提前预处理好的值即可。一定要注意边权转成点权之后要排除
时间复杂度为
:::success[核心代码]
struct Querys{ll op,x,y;}q[N];
ll t,n,u[N],v[N],w[N],dfn[N],T,sz[N],dep[N],bl[N],L[N],R[N],ans[N];
ll fa[N],id[N],tot,near[N],b[N],wt[N],chs,qtot,up[N][Lg];
vector<pair<ll,ll> > e[N];
vector<ll> tmp;
bool vis[N];
string s;
inline void dfs1(ll u,ll f){
dfn[u]=++T,sz[u]=1,fa[u]=f,dep[u]=dep[f]+1,b[dep[u]%B]++;
for(auto [v,_w]:e[u]) if(v!=f) wt[v]=_w,dfs1(v,u),sz[u]+=sz[v];
return;
}
inline void dfs2(ll u){
if(dep[u]%B==chs) id[u]=++tot;
near[u]=(id[u]?u:near[fa[u]]);
for(auto [v,_w]:e[u]) if(v!=fa[u]) dfs2(v);
return;
}
inline ll lca(ll x,ll y){
if(dep[x]<dep[y]) swap(x,y);
ll p=dep[x]-dep[y];
for(int j=Lg-1;~j;j--) if((p>>j)&1) x=up[x][j];
if(x==y) return x;
for(int j=Lg-1;~j;j--) if(up[x][j]!=up[y][j]) x=up[x][j],y=up[y][j];
return fa[x];
}
inline void rebuild(){
for(int i=1;i<=n;i++) if(id[i]){
ll fi=near[fa[i]];ans[id[i]]=0;
for(int j=i;j!=fi;j=fa[j]) if(!vis[j]) ans[id[i]]=max(ans[id[i]],wt[j]);
}
return;
}
inline ll query(ll u,ll v){
ll Ans=0,now=u;
if(dep[near[u]]<dep[v]) for(int i=u;i!=v;i=fa[i]) Ans=max(Ans,(vis[i]?0:wt[i]));
else{
while(!id[now]) Ans=max(Ans,(vis[now]?0:wt[now])),now=fa[now];
while(dep[near[fa[now]]]>dep[v]) Ans=max(Ans,ans[id[now]]),now=near[fa[now]];
while(now!=v) Ans=max(Ans,(vis[now]?0:wt[now])),now=fa[now];
}
for(auto x:tmp) if((dfn[x]>dfn[v])&&(dfn[x]<dfn[v]+sz[v])&&(dfn[u]>=dfn[x])&&(dfn[u]<dfn[x]+sz[x])) Ans=max(Ans,wt[x]);
return Ans;
}
inline void Clear(){
for(int i=1;i<=n;i++) dfn[i]=b[i]=wt[i]=near[i]=id[i]=fa[i]=ans[i]=sz[i]=dep[i]=vis[i]=0,e[i].clear();
return T=tot=b[0]=0,tmp.clear(),void();
}
int main(){
read(t);
while(t--){
read(n);
for(int i=1;i<n;i++){
read(u[i]),read(v[i]),read(w[i]);
e[u[i]].push_back({v[i],w[i]});
e[v[i]].push_back({u[i],w[i]});
}
dfs1(1,0),chs=min_element(b,b+B)-b,dfs2(1);
for(int i=1;i<=n;i++) up[i][0]=fa[i];
for(int j=1;j<Lg;j++) for(int i=1;i<=n;i++) up[i][j]=up[up[i][j-1]][j-1];
for(qtot=1;;qtot++){
read(s);
if(s=="DONE") break;
else if(s=="QUERY") q[qtot].op=1;
else q[qtot].op=2;
read(q[qtot].x),read(q[qtot].y);
}
qtot--;
for(int i=1;i<=qtot;i++) bl[i]=(i-1)/B+1;
for(int i=1;i<=bl[qtot];i++) L[i]=R[i-1]+1,R[i]=min(qtot,i*B);
for(int Qid=1;Qid<=bl[qtot];Qid++){
tmp.clear();
for(int i=1;i<=n;i++) vis[i]=false;
ll l=L[Qid],r=R[Qid];
for(int i=l;i<=r;i++) if(q[i].op==2){
ll U=u[q[i].x],V=v[q[i].x];
if(dep[U]<dep[V]) swap(U,V);
if(!vis[U]) tmp.push_back(U);
vis[U]=true;
}
rebuild();
for(int i=l;i<=r;i++){
if(q[i].op==2){
ll U=u[q[i].x],V=v[q[i].x];
if(dep[U]<dep[V]) swap(U,V);
wt[U]=q[i].y;
}
else{
ll _lca=lca(q[i].x,q[i].y);
if(q[i].x==q[i].y) write(0,'\n');
else if(_lca==q[i].y) write(query(q[i].x,q[i].y),'\n');
else if(_lca==q[i].x) write(query(q[i].y,q[i].x),'\n');
else write(max(query(q[i].x,_lca),query(q[i].y,_lca)),'\n');
}
}
}
Clear();
}
return 0;
}
:::
六、QTREE6
1、题目链接
luogu RMJ 链接
SPOJ 链接
2、题意简述
给定一棵
1 x:将节点x 的颜色反转。2 x:输出x 所在的同颜色连通块大小。
3、思路简析
此时,查询操作来到了连通块上。再树分块就不合适了。因为这种树分块只能处理链上的信息,不能处理连通块信息。
我们还是考虑操作序列分块。暂存操作,每
统一处理
现在,我们将所有由确定点诱导的同色连通块集合缩成一个点,并在所有性质不同的点集之间,以及两个不确定点之间连一条边。其中一个点集的性质,指它是确定的,还是不确定的。如图:
右图是缩点后的样子。
那么对于一个确定点集,我们分情况讨论:
- 它的度数为
0 ,即孤立点集。从它开始不可能走到其它集合里。 - 它的度数为
1 ,即叶子点集。此时我们对于所有不确定点,维护一个sum_0 和sum_1 ,分别表示它的所有儿子节点中,黑色叶子点集的大小之和,以及所有白色叶子点集的大小之和。 - 它的度数至少为
2 。此时保留这整个块,不做任何处理。
经典的,此时图中最多有
缩点和删边之后是一片森林。设有
又因为不确定点的数量最多是
那么对于每次询问,暴力 DFS 到相邻颜色的连通块即可。每次遍历到不确定点,记得加上叶子点集的集合大小。
如果查询的节点已经被折叠(情况
时间复杂度
:::success[核心代码]
ll n,m,u,v,T,tot,op[N],x[N],dfn[N],fa[N],par[N];
ll rep[N],sz[N],deg[N],bel[N],sum[N][2];
vector<ll> e[N],g[N],cg;
vector<pair<ll,ll> > Bp;
bool col[N],used[N];
inline void dfs1(ll u,ll f){
fa[u]=f,dfn[u]=++T,par[T]=dfn[fa[u]];
for(auto v:e[u]) if(v!=f) dfs1(v,u);
return;
}
inline void add(ll u,ll v){return g[u].push_back(v),g[v].push_back(u),void();}
inline void rebuild(){
tot=0,Bp.clear();
for(int u=1;u<=n;u++){
ll p=par[u];
if(p&&!used[u]&&!used[p]&&col[u]==col[p]) rep[u]=rep[p];
else{
rep[u]=u,sz[u]=deg[u]=0,g[u].clear();
if(used[u]) sum[u][0]=sum[u][1]=0;
}
sz[rep[u]]++;
if(!p) continue;
if(used[u]&&used[p]) add(u,p);
else if(used[u]^used[p]){
ll v=(used[u]?rep[p]:rep[u]),w=(used[u]?u:p);
deg[v]++,bel[v]=w,Bp.push_back({v,w});
}
}
for(auto [v,w]:Bp){
if(deg[v]==1) sum[w][col[v]]+=sz[v];
else add(v,w);
}
return;
}
inline ll dfs2(ll u,ll f){
ll ans=(used[u]?1+sum[u][col[u]]:sz[u]);
for(auto v:g[u]) if(v!=f&&col[v]==col[u]) ans+=dfs2(v,u);
return ans;
}
inline ll query(ll u){
ll v=rep[u];
if(used[u]||deg[v]>=2) return dfs2(v,0);
if(deg[v]==0||col[v]!=col[bel[v]]) return sz[v];
return dfs2(bel[v],0);
}
int main(){
read(n);
for(int i=1;i<n;i++) read(u),read(v),e[u].push_back(v),e[v].push_back(u);
dfs1(1,0);
read(m);
for(int i=1;i<=m;i++) read(op[i]),read(x[i]),x[i]=dfn[x[i]];
for(int l=1;l<=m;l+=B){
ll r=min(l+B-1,m);
cg.clear();
for(int i=l;i<=r;i++) if(op[i]&&!used[x[i]]) used[x[i]]=true,cg.push_back(x[i]);
rebuild();
for(int i=l;i<=r;i++){
if(op[i]) col[x[i]]^=1;
else write(query(x[i]),'\n');
}
for(auto x:cg) used[x]=false;
}
return 0;
}
:::
七、QTREE7
1、题目链接
luogu RMJ 链接
SPOJ 链接
2、题意简述
给定一棵
1 x:将节点x 的颜色反转。2 x w:将节点x 的点权改为w 。3 x:输出x 所在的同颜色连通块中点权的最大值。
3、思路简析
跟上一个题一模一样。把上一个题维护的集合大小信息全部换成点权最大值即可。要注意翻色或修改点权的点都算不确定点。以及空集合的最大值用
:::success[核心代码]
ll n,m,u,v,T,p,tot,a[N],w[N],val[N],op[N],x[N],dfn[N],fa[N],par[N];
ll rep[N],mx[N],deg[N],bel[N],best[N][2];
vector<ll> e[N],g[N],cg;
vector<pair<ll,ll> > Bp;
bool col[N],used[N];
inline void dfs1(ll u,ll f){
fa[u]=f,dfn[u]=++T,par[T]=dfn[fa[u]];
for(auto v:e[u]) if(v!=f) dfs1(v,u);
return;
}
inline void add(ll u,ll v){return g[u].push_back(v),g[v].push_back(u),void();}
inline void rebuild(){
tot=0,Bp.clear();
for(int u=1;u<=n;u++){
ll p=par[u];
if(p&&!used[u]&&!used[p]&&col[u]==col[p]) rep[u]=rep[p];
else{
rep[u]=u,mx[u]=-inf,deg[u]=0,g[u].clear();
if(used[u]) best[u][0]=best[u][1]=-inf;
}
mx[rep[u]]=max(mx[rep[u]],val[u]);
if(!p) continue;
if(used[u]&&used[p]) add(u,p);
else if(used[u]^used[p]){
ll v=(used[u]?rep[p]:rep[u]),w=(used[u]?u:p);
deg[v]++,bel[v]=w,Bp.push_back({v,w});
}
}
for(auto [v,w]:Bp){
if(deg[v]==1) best[w][col[v]]=max(best[w][col[v]],mx[v]);
else add(v,w);
}
return;
}
inline ll dfs2(ll u,ll f){
ll ans=(used[u]?max(val[u],best[u][col[u]]):mx[u]);
for(auto v:g[u]) if(v!=f&&col[v]==col[u]) ans=max(ans,dfs2(v,u));
return ans;
}
inline ll query(ll u){
ll v=rep[u];
if(used[u]||deg[v]>=2) return dfs2(v,0);
if(deg[v]==0||col[v]!=col[bel[v]]) return mx[v];
return dfs2(bel[v],0);
}
int main(){
read(n);
for(int i=1;i<n;i++) read(u),read(v),e[u].push_back(v),e[v].push_back(u);
dfs1(1,0);
for(int i=1;i<=n;i++) read(p),col[dfn[i]]=p;
for(int i=1;i<=n;i++) read(val[dfn[i]]);
read(m);
for(int i=1;i<=m;i++){
read(op[i]),read(x[i]),x[i]=dfn[x[i]];
if(op[i]==2) read(w[i]);
}
for(int l=1;l<=m;l+=B){
ll r=min(l+B-1,m);
cg.clear();
for(int i=l;i<=r;i++) if(op[i]&&!used[x[i]]) used[x[i]]=true,cg.push_back(x[i]);
rebuild();
for(int i=l;i<=r;i++){
if(op[i]==1) col[x[i]]^=1;
else if(op[i]==2) val[x[i]]=w[i];
else write(query(x[i]),'\n');
}
for(auto x:cg) used[x]=false;
}
return 0;
}
:::
八、QTREE4
1、题目链接
luogu RMJ 链接
luogu 主题库链接
SPOJ 链接
2、题意简述
给定一棵
1 x:将节点x 的颜色反转。2:输出现在最远的两个白色节点的距离。
3、思路简析
有点懵,但是不管了,先操作序列分块了再说。
暂存操作,每
统一处理
对于一次查询,我们将答案对应的两个白点分成三种情况:
- 两个点都是确定点。可以先提前做一次树形 DP 求出。
- 其中一个点是不确定点。我们提前用树形 DP 预处理出距离每个点最远的确定白点的距离。此时因为我们存了
B 个操作,所以最多有B 个不确定点。暴力遍历所有不确定点,查表更新答案即可。时间复杂度O(B) 。 - 两个点都是不确定点。我们把所有不确定点单独拿出来建一棵虚树,边权为原树上路径的边权和,再做一次 DP 求出此时的直径即可。时间复杂度
O(B) 。
每批操作建一次虚树,每次查询跑一次 DP。建虚树时每批要按 DFS 序排序,
总时间复杂度
:::success[核心代码]
ll n,q,T,cnt,fans,ans,u,v,w;
ll fa[N],dfn[N],sz[N],dis[N],up[N][Lg],op[Q],dep[N];
ll down[N],sec[N],son[N],Up[N];
bool wh[N],vis[N];
char c;
vector<pair<ll,ll> > e[N];
vector<vector<ll> > ve;
vector<ll> a,vfa,vw;
inline void dfs1(ll u,ll f){
fa[u]=f,dfn[u]=++T,sz[u]=1,dep[u]=dep[f]+1;
for(auto [v,w]:e[u]) if(v!=f) dis[v]=dis[u]+w,dfs1(v,u),sz[u]+=sz[v];
return;
}
inline ll lca(ll u,ll v){
if(dep[u]<dep[v]) swap(u,v);
ll k=dep[u]-dep[v];
for(int j=Lg-1;~j;j--) if((k>>j)&1) u=up[u][j];
if(u==v) return u;
for(int j=Lg-1;~j;j--) if(up[u][j]!=up[v][j]) u=up[u][j],v=up[v][j];
return fa[u];
}
inline void dfsD(ll u){
down[u]=(wh[u]&&!vis[u]?0:-inf),sec[u]=-inf,son[u]=0;
fans=max(fans,down[u]);
for(auto [v,w]:e[u]) if(v!=fa[u]){
dfsD(v);
if(down[v]==-inf) continue;
ll t=down[v]+w;
if(down[u]!=-inf) fans=max(fans,down[u]+t);
if(t>down[u]) sec[u]=down[u],down[u]=t,son[u]=v;
else sec[u]=max(sec[u],t);
}
return;
}
inline void dfsU(ll u){
for(auto [v,w]:e[u]) if(v!=fa[u]){
ll t=max(Up[u],(son[u]==v?sec[u]:down[u]));
Up[v]=(t==-inf?-inf:t+w);
dfsU(v);
}
return;
}
inline void build(){
sort(a.begin(),a.end(),[](const ll &u,const ll &v){return dfn[u]<dfn[v];});
ll m=a.size();
for(int i=1;i<m;i++) a.push_back(lca(a[i-1],a[i]));
sort(a.begin(),a.end(),[](const ll &u,const ll &v){return dfn[u]<dfn[v];});
a.erase(unique(a.begin(),a.end()),a.end());
vfa.resize(a.size()),vw.resize(a.size()),ve.clear(),ve.resize(a.size());
for(int i=1;i<(ll)a.size();i++){
ll f=i-1;
while(dfn[a[i]]<dfn[a[f]]||dfn[a[i]]>=dfn[a[f]]+sz[a[f]]) f=vfa[f];
vfa[i]=f,vw[i]=dis[a[i]]-dis[a[f]],ve[f].push_back(i);
}
return;
}
inline ll DP(ll x){
ll u=a[x],mx=-inf;
if(vis[u]&&wh[u]) mx=0,ans=max(ans,max(Up[u],down[u]));
for(int i:ve[x]){
ll t=DP(i);
if(t==-inf) continue;
t+=vw[i];
if(mx!=-inf) ans=max(ans,mx+t);
mx=max(mx,t);
}
return mx;
}
int main(){
read(n);
for(int i=1;i<n;i++) read(u),read(v),read(w),e[u].push_back({v,w}),e[v].push_back({u,w});
dfs1(1,0);
for(int i=1;i<=n;i++) up[i][0]=fa[i];
for(int j=1;j<Lg;j++) for(int i=1;i<=n;i++) up[i][j]=up[up[i][j-1]][j-1];
read(q);
for(int i=1;i<=q;i++){
read(c);
if(c=='C') read(op[i]);
}
cnt=n;
for(int i=1;i<=n;i++) wh[i]=true;
a.reserve(2*B);
for(int l=1;l<=q;l+=B){
ll r=min(q,l+B-1);
bool flag=false,cf=false;
a.clear();
for(int i=l;i<=r;i++){
if(!op[i]) flag=true;
else if(!vis[op[i]]) vis[op[i]]=true,a.push_back(op[i]);
}
if(flag) fans=Up[1]=-inf,dfsD(1),dfsU(1),build();
for(int i=l;i<=r;i++){
if(op[i]) cnt+=(wh[op[i]]?-1:1),wh[op[i]]^=1,cf=false;
else if(!cnt) ps("They have disappeared.\n");
else{
if(!cf){
ans=max(0,fans),cf=true;
if(!a.empty()) DP(0);
}
write(ans,'\n');
}
}
for(auto u:a) vis[u]=false;
}
return 0;
}
:::