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

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

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

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

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

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

 

#include
     
      #include
      
       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
       
        >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]
        
         >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