这是常规的使用线段树超时：

1 #pragma comment(linker, "/STACK:16777216")  2 #include
     
        3 #include
      
         4 long long ans[2][100005];  5 int next[200005],head[100005],point[200005];  6 int num[100005],father[100005],son[100005],deep[100005],top[100005],tree[100005],pre[100005];  7 long long setv[2][400005];  8 int now,cnt;  9 void add(int x,int y) 10 { 11     next[++now]=head[x]; 12     head[x]=now; 13     point[now]=y; 14 } 15 void dfs1(int u) 16 { 17     num[u]=1; 18     for (int i=head[u];i!=-1;i=next[i]) 19     { 20         int v=point[i]; 21         if (v==father[u]) continue; 22         father[v]=u; 23         deep[v]=deep[u]+1; 24         dfs1(v); 25         num[u]+=num[v]; 26         if (son[u]==-1||num[son[u]]
       
        =r) { 45         setv[kind][o]+=d; 46         return; 47     } 48     if (setv[kind][o]!=0) 49     { 50         setv[kind][o*2]+=setv[kind][o]; 51         setv[kind][o*2+1]+=setv[kind][o]; 52         setv[kind][o]=0; 53     } 54     int mid=l+(r-l)/2; 55     if (y1<=mid) update(o*2,l,mid,kind,y1,y2,d); 56     if (y2>mid) update(o*2+1,mid+1,r,kind,y1,y2,d); 57 } 58 //int query(int o,int l,int r,int kind,int y) 59 void query(int o,int l,int r) 60 { 61     if (l==r) {ans[0][pre[l]]=setv[0][o]; ans[1][pre[l]]=setv[1][o]; return; } 62     if (setv[0][o]!=0) 63     { 64         setv[0][o*2]+=setv[0][o]; 65         setv[0][o*2+1]+=setv[0][o]; 66         setv[0][o]=0; 67     } 68      if (setv[1][o]!=0) 69     { 70         setv[1][o*2]+=setv[1][o]; 71         setv[1][o*2+1]+=setv[1][o]; 72         setv[1][o]=0; 73     } 74     int mid=l+(r-l)/2; 75     query(o*2,l,mid); 76     query(o*2+1,mid+1,r); 77 } 78 void change(int kind,int l,int r,long long d) 79 { 80     int temp; 81     while (top[l]!=top[r]) 82     { 83         if (deep[top[l]]
        
         deep[r]) {temp=l; l=r; r=temp; } 88     if (kind==0) update(1,1,cnt,kind,tree[l],tree[r],d); 89     else update(1,1,cnt,kind,tree[son[l]],tree[r],d); 90 } 91 void scanf ( int& x , char c = 0 , int flag = 0 ) { 92     while ( ( c = getchar () ) != '-' && ( c < '0' || c > '9' ) ) ; 93     if ( c == '-' ) flag = 1 , x = 0 ; 94     else x = c - '0' ; 95     while ( ( c = getchar () ) >= '0' && c <= '9' ) x = x * 10 + c - '0' ; 96     if ( flag ) x = -x ; 97 } 98 int main() 99 {100     int T,t,i,x,y,d,l,r,n,m;101     char s[5];102     scanf("%d",&T);103     for (t=1;t<=T;t++)104     {105         now=0; cnt=0;106         memset(head,-1,sizeof(head));107         memset(son,-1,sizeof(son));108         memset(setv,0,sizeof(setv));109         deep[1]=1; father[1]=1;110         scanf("%d%d",&n,&m);111         for (i=1;i
        
       
      
     

因为是单次查询全部，所以可以累加变量，快了许多：

1 #pragma comment(linker, "/STACK:16777216")  2 #include
     
        3 #include
      
         4 long long ans[2][100005];  5 int n;  6 int next[200005],head[100005],point[200005];  7 int num[100005],father[100005],son[100005],deep[100005],top[100005],tree[100005],pre[100005];  8 long long setv[2][200005];  9 int now,cnt; 10 void add(int x,int y) 11 { 12     next[++now]=head[x]; 13     head[x]=now; 14     point[now]=y; 15 } 16 void dfs1(int u) 17 { 18     num[u]=1; 19     for (int i=head[u];i!=-1;i=next[i]) 20     { 21         int v=point[i]; 22         if (v==father[u]) continue; 23         father[v]=u; 24         deep[v]=deep[u]+1; 25         dfs1(v); 26         num[u]+=num[v]; 27         if (son[u]==-1||num[son[u]]
       
        deep[r]) {temp=l; l=r; r=temp; } 63     if (kind==0) {setv[0][tree[l]]+=d; setv[0][tree[r]+1]-=d;} 64     else {setv[1][tree[son[l]]]+=d; setv[1][tree[r]+1]-=d;} 65 } 66 void scanf ( int& x , char c = 0 , int flag = 0 ) { 67     while ( ( c = getchar () ) != '-' && ( c < '0' || c > '9' ) ) ; 68     if ( c == '-' ) flag = 1 , x = 0 ; 69     else x = c - '0' ; 70     while ( ( c = getchar () ) >= '0' && c <= '9' ) x = x * 10 + c - '0' ; 71     if ( flag ) x = -x ; 72 } 73 int main() 74 { 75     int T,t,i,x,y,d,l,r,m; 76     char s[5]; 77     scanf("%d",&T); 78     for (t=1;t<=T;t++) 79     { 80         now=0; cnt=0; 81         memset(head,-1,sizeof(head)); 82         memset(son,-1,sizeof(son)); 83         memset(setv,0,sizeof(setv)); 84         deep[1]=1; father[1]=1; 85         scanf("%d%d",&n,&m); 86         for (i=1;i