树分治,对于每个分治结构,维护两棵线段树。

第一棵按dfs序维护所有点到重心的距离,第二棵维护每个分支的最长链。

那么当前结构对答案的贡献就是第二棵线段树的最大值$+$次大值。

对于操作$0$,如果是激活某个点,则直接把它距离$+=inf$,隐藏某个点则是$-=inf$。

对于操作$1$,相当于子树全部加上一个值,进行区间加即可。

时间复杂度$O(n\log^2n)$。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010,M=262150,inf=1000000000;
int n,m,i,j,e[N][3],ex[N],active,q[N][3],ans[N],tag[M];
int g[N],v[N<<1],w[N<<1],ok[N<<1],nxt[N<<1],ed,G[N],NXT[N];
int son[N],f[N],all,now;
inline void read(int&a){
char c;bool f=0;a=0;
while(!((((c=getchar())>='0')&&(c<='9'))||(c=='-')));
if(c!='-')a=c-'0';else f=1;
while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';
if(f)a=-a;
}
inline void umax(int&a,int b){if(a<b)a=b;}
void build(int x,int a,int b){
tag[x]=-inf;
if(a==b)return;
int mid=(a+b)>>1;
build(x<<1,a,mid),build(x<<1|1,mid+1,b);
}
void change(int x,int a,int b,int c,int d,int p){
if(c<=a&&b<=d){umax(tag[x],p);return;}
int mid=(a+b)>>1;
if(c<=mid)change(x<<1,a,mid,c,d,p);
if(d>mid)change(x<<1|1,mid+1,b,c,d,p);
}
void print(int x,int a,int b){
if(a==b){
if(q[a][0]==2){
if(ans[a]==1)puts("Nothing..Nothing!");
else if(ans[a]==2)puts("Only one baby!");
else printf("%d\n",tag[x]);
}
return;
}
int mid=(a+b)>>1;
umax(tag[x<<1],tag[x]);
umax(tag[x<<1|1],tag[x]);
print(x<<1,a,mid),print(x<<1|1,mid+1,b);
}
inline void add(int x,int y,int z){v[++ed]=y;w[ed]=z;ok[ed]=1;nxt[ed]=g[x];g[x]=ed;}
inline void ADD(int x,int y){NXT[y]=G[x];G[x]=y;}
void findroot(int x,int y){
son[x]=1;f[x]=0;
for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=y){
findroot(v[i],x);
son[x]+=son[v[i]];
if(son[v[i]]>f[x])f[x]=son[v[i]];
}
if(all-son[x]>f[x])f[x]=all-son[x];
if(f[x]<f[now])now=x;
}
int tmp,cur,edge[N],from[N],vis[N];
int d[N],st[N],en[N],dfn,ST[N],EN[N],cp,pool[N];
namespace Node{
int q[N],v[M],tag[M];
inline void tag1(int x,int p){v[x]+=p;tag[x]+=p;}
inline void pb(int x){if(tag[x])tag1(x<<1,tag[x]),tag1(x<<1|1,tag[x]),tag[x]=0;}
inline void up(int x){v[x]=max(v[x<<1],v[x<<1|1]);}
void build(int x,int a,int b){
tag[x]=0;
if(a==b){v[x]=q[a];return;}
int mid=(a+b)>>1;
build(x<<1,a,mid),build(x<<1|1,mid+1,b),up(x);
}
void add(int x,int a,int b,int c,int d,int p){
if(c<=a&&b<=d){tag1(x,p);return;}
pb(x);
int mid=(a+b)>>1;
if(c<=mid)add(x<<1,a,mid,c,d,p);
if(d>mid)add(x<<1|1,mid+1,b,c,d,p);
up(x);
}
int ask(int x,int a,int b,int c,int d){
if(c<=a&&b<=d)return v[x];
pb(x);
int mid=(a+b)>>1,t=-inf;
if(c<=mid)t=ask(x<<1,a,mid,c,d);
if(d>mid)umax(t,ask(x<<1|1,mid+1,b,c,d));
up(x);
return t;
}
}
namespace Sub{
int q[N],fir[M],sec[M];
inline void up(int x){
if(fir[x<<1]>fir[x<<1|1]){
fir[x]=fir[x<<1];
sec[x]=max(sec[x<<1],fir[x<<1|1]);
}else{
fir[x]=fir[x<<1|1];
sec[x]=max(fir[x<<1],sec[x<<1|1]);
}
}
void build(int x,int a,int b){
if(a==b){fir[x]=q[a];sec[x]=-inf;return;}
int mid=(a+b)>>1;
build(x<<1,a,mid),build(x<<1|1,mid+1,b),up(x);
}
void change(int x,int a,int b,int c,int p){
if(a==b){fir[x]=p;return;}
int mid=(a+b)>>1;
if(c<=mid)change(x<<1,a,mid,c,p);else change(x<<1|1,mid+1,b,c,p);
up(x);
}
}
inline void init(int x){
from[x]=cur;
vis[x]=now;
ex[x]=1;
for(int i=G[x];i;i=NXT[i])pool[++cp]=i;
}
void dfs(int x,int y,int z,int dep){
umax(tmp,z);
d[x]=dep;
st[x]=++dfn;
Node::q[dfn]=z;
init(x);
for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=y)edge[i>>1]=w[i],dfs(v[i],x,z+w[i],dep+1);
en[x]=dfn;
}
inline void update(int l,int r){
if(l>r)return;
int t=Sub::sec[1];
if(ex[now])umax(t,0);
change(1,1,m,l,r,Sub::fir[1]+t);
}
void solve(int x){
int i;
cur=cp=dfn=d[x]=0;
init(x);
for(i=g[x];i;i=nxt[i])if(ok[i]){
edge[i>>1]=w[i];
cur++;
tmp=-inf;
ST[cur]=dfn+1;
dfs(v[i],x,w[i],1);
EN[cur]=dfn;
Sub::q[cur]=tmp;
}
if(!cur)return;
Node::build(1,1,dfn);
Sub::build(1,1,cur);
sort(pool+1,pool+cp+1);
pool[cp+1]=m+1;
update(1,pool[1]-1);
for(i=1;i<=cp;i++){
int A=q[pool[i]][0],B=q[pool[i]][1],C=q[pool[i]][2];
if(!A){
if(B==now){
ex[now]^=1;
update(pool[i],pool[i+1]-1);
continue;
}
if(ex[B])Node::add(1,1,dfn,st[B],st[B],-inf);
else Node::add(1,1,dfn,st[B],st[B],inf);
Sub::change(1,1,cur,from[B],Node::ask(1,1,dfn,ST[from[B]],EN[from[B]]));
ex[B]^=1;
}else{
if(vis[e[B][0]]!=now||vis[e[B][1]]!=now){
update(pool[i],pool[i+1]-1);
continue;
}
int z=d[e[B][0]]>d[e[B][1]]?e[B][0]:e[B][1];
Node::add(1,1,dfn,st[z],en[z],C-=edge[B]);
Sub::change(1,1,cur,from[z],Node::ask(1,1,dfn,ST[from[z]],EN[from[z]]));
edge[B]+=C;
}
update(pool[i],pool[i+1]-1);
}
for(i=g[x];i;i=nxt[i])if(ok[i]){
ok[i^1]=0;
f[0]=all=son[v[i]];
findroot(v[i],now=0);
solve(now);
}
}
int main(){
read(n);
for(ed=i=1;i<n;i++){
for(j=0;j<3;j++)read(e[i][j]);
add(e[i][0],e[i][1],e[i][2]);
add(e[i][1],e[i][0],e[i][2]);
}
read(m);
for(i=1;i<=n;i++)ex[i]=1;
for(active=n,i=1;i<=m;i++){
read(q[i][0]);
if(q[i][0]<2)read(q[i][1]);
if(q[i][0]==1)read(q[i][2]);
if(!q[i][0]){
if(ex[q[i][1]])active--;else active++;
ex[q[i][1]]^=1;
ADD(q[i][1],i);
}
if(q[i][0]==1)ADD(e[q[i][1]][0],i);
if(q[i][0]==2){
if(active==0)ans[i]=1;
if(active==1)ans[i]=2;
}
}
build(1,1,m);
f[0]=all=n;findroot(1,now=0);solve(now);
print(1,1,m);
return 0;
}

  

最新文章

  1. AWS 免费套餐
  2. EQueue - 一个纯C#写的分布式消息队列介绍2
  3. name after, name for, name as
  4. C++ 关联容器
  5. poj 1067 取石子游戏(威佐夫博奕(Wythoff Game))
  6. 变色龙安装程序 Chameleon Install 2.2 svn 2281发布
  7. 动手实践:在Windows上安装NumPy、Matplotlib、SciPy和IPython
  8. 宝洁的Pvp
  9. CSS之可收缩的底部边框
  10. Sublime Text 3 LESS、SASS、SCSS高亮插件、提示插件
  11. JVM基础(3)-多态性实现机制
  12. 原创:LoadTest系列之Insert Condition
  13. RPC漏洞
  14. python 闭包初识
  15. Java 疑问自问自答
  16. PAT甲级1091 Acute Stroke【三维bfs】
  17. java 虹软ArcFace 2.0,java SDK使用-进行人脸检测
  18. opencv输出图片像素值
  19. odoo 打印格式中 打印第一个数据默认
  20. VB ASP 使用 now() 时默认格式调整方法

热门文章

  1. checkbox复选框全选
  2. IOS开发之实现App消息推送
  3. NYOJ题目125盗梦空间
  4. jq点击和鼠标移上效果以及一个等号&quot;=&quot; 二个等号&quot;==&quot; 三个等号&quot;===&quot; 的区别
  5. jquery文件上传控件 Uploadify 问题记录
  6. HTTP 请求头中的 X-Forwarded-For
  7. 同一服务器配置DataGuard
  8. HDU1899 Sum the K-th&#39;s(树状数组)
  9. Multiple types were found that match the controller named &#39;Home&#39;. (weird error)
  10. Solr入门之(2)快速启动:第一个例子