一个点的感染时间为它到根路径上虚边数+1。

用Link-Cut Tree模拟虚实边切换，每次切换时等价于在一段或两段DFS序区间更新，线段树维护即可。

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

 

#include
     
      typedef long long ll;const int N=100010,M=262145;int n,m,i,x,y,root;int g[N],nxt[N<<1],v[N<<1],ed;int top[N],child[N],fa[N],d[N],size[N],st[N],en[N],dfn,seq[N];inline void addedge(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}inline void swap(int&a,int&b){int c=a;a=b;b=c;}inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}int tag[M];ll val[M];inline void add1(int x,int a,int b,int p){val[x]+=(ll)(b-a+1)*p;tag[x]+=p;}inline void pb(int x,int a,int b){  if(tag[x]){    int mid=(a+b)>>1;    add1(x<<1,a,mid,tag[x]),add1(x<<1|1,mid+1,b,tag[x]),tag[x]=0;  }}inline void up(int x){val[x]=val[x<<1]+val[x<<1|1];}void build(int x,int a,int b){  if(a==b){val[x]=seq[a];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 d,int p){  if(c>d)return;  if(c<=a&&b<=d){add1(x,a,b,p);return;}  pb(x,a,b);  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);  up(x);}ll ask(int x,int a,int b,int c,int d){  if(c>d)return 0;  if(c<=a&&b<=d)return val[x];  pb(x,a,b);  int mid=(a+b)>>1;ll t=0;  if(c<=mid)t=ask(x<<1,a,mid,c,d);  if(d>mid)t+=ask(x<<1|1,mid+1,b,c,d);  return up(x),t;}inline int lca2(int x,int y){  int t;  while(top[x]!=top[y])t=top[x],x=fa[top[x]];  return x==y?t:child[y];}inline void subadd(int x,int p){  if(x==root){change(1,1,n,1,n,p);return;}  if(st[x]>st[root]||en[x]
      
       st[root]||en[x]
       
        sizemax)sizemax=size[v[i]],heavy=v[i];  }  if(heavy)child[x]=heavy;}void dfs2(int x,int pre,int t){  st[x]=++dfn;seq[dfn]=d[x];top[x]=t;  if(child[x])dfs2(child[x],x,t);  for(int i=g[x];i;i=nxt[i])if(v[i]!=pre&&v[i]!=child[x])dfs2(v[i],x,v[i]);  en[x]=dfn;}char op[10];int main(){  read(n);read(m);  for(i=1;i