Description

给定一棵结点数为n的树，初始点权均为0，有依次q个操作，每次操作有三个参数a,b,c，当a=1时，表示给b号结点到c号结点路径上的所有点（包括b,c，下同）权值都增加1，当a=2时，表示询问b号结点到c号结点路径上的所有点权值之和。

Input

第一行，一个正整数n。

接下来n-1行，每行一对正整数x,y，表示x号结点和y号结点之间有一条边。

第n+1行，一个正整数q。

最后q行，每行一组正整数a,b,c，表示操作的三个参数。b和c可能相等。

保证数据都是合法的。

Output

若干行，每行一个非负整数表示答案。

Sample Input

5

1 2

2 3

1 4

2 5

5

1 4 5

2 1 5

1 1 3

2 5 3

2 4 3

Sample Output

3

4

6

 

题解：

如题名，数剖练习题。

 

代码：

1 var  2   son,siz,dep,top,w,fa,tt2,c,flag:array[-1..200001]of longint;  3   tt:array[-1..400001,-2..2]of longint;  4   b:array[-1..200001,1..2]of longint;  5   i,j,k,l,n,m,totw,q,t:longint;  6 function cc2(x,l,r:longint):longint;  7 begin  8   cc2:=0; cc2:=cc2+(r-l+1)*tt[x,0];  9   if tt[x,1]=tt[x,2] then exit; 10   if r<=(tt[x,1]+tt[x,2])div 2 then cc2:=cc2+cc2(tt[x,-1],l,r)else 11   if l>(tt[x,1]+tt[x,2])div 2 then cc2:=cc2+cc2(tt[x,-2],l,r)else 12   begin cc2:=cc2+cc2(tt[x,-1],l,(tt[x,1]+tt[x,2])div 2); 13   cc2:=cc2+cc2(tt[x,-2],((tt[x,1]+tt[x,2])div 2)+1,r); end; 14 end; 15 procedure cc1(x,l,r:longint); 16 begin 17   if(l=tt[x,1])and(r=tt[x,2])then 18   begin tt[x,0]:=tt[x,0]+1; exit; end; 19   if r<=(tt[x,1]+tt[x,2])div 2 then cc1(tt[x,-1],l,r)else 20   if l>(tt[x,1]+tt[x,2])div 2 then cc1(tt[x,-2],l,r)else 21   begin cc1(tt[x,-1],l,(tt[x,1]+tt[x,2])div 2); 22   cc1(tt[x,-2],((tt[x,1]+tt[x,2])div 2)+1,r); end; 23 end; 24 procedure ss(z,x,y:longint); 25 var i,j,k,l,f1,f2,tot:longint; 26 begin 27   f1:=top[x]; f2:=top[y]; tot:=0; 28   while f1<>f2 do 29   begin 30     if dep[f1]
      
       w[y] then begin j:=x; x:=y; y:=j; end; 36   if z=1 then cc1(1,w[x],w[y])else 37   begin tot:=tot+cc2(1,w[x],w[y]); writeln(tot); end; 38 end; 39 procedure dfs2(x:longint); 40 var i,j,k,l:longint; 41 begin 42   j:=c[x]; 43   while b[j,1]=x do 44   begin 45     if b[j,2]=son[x] then 46     begin 47       flag[b[j,2]]:=1; top[b[j,2]]:=top[x]; 48       inc(totw); w[b[j,2]]:=totw; tt2[totw]:=b[j,2]; 49       dfs2(b[j,2]); 50     end; 51     inc(j); 52   end; 53   j:=c[x]; 54   while b[j,1]=x do 55   begin 56     if flag[b[j,2]]=0 then 57     begin 58       flag[b[j,2]]:=1; top[b[j,2]]:=b[j,2]; 59       inc(totw); w[b[j,2]]:=totw; tt2[totw]:=b[j,2]; 60       dfs2(b[j,2]); 61     end; 62     inc(j); 63   end; 64 end; 65 procedure dfs1(x:longint); 66 var i,j,k,l:longint; 67 begin 68   j:=c[x]; siz[x]:=1; 69   while b[j,1]=x do 70   begin 71     if fa[b[j,2]]=0 then 72     begin 73       fa[b[j,2]]:=x; 74       dep[b[j,2]]:=dep[x]+1; 75       dfs1(b[j,2]); siz[x]:=siz[x]+siz[b[j,2]]; 76       if(son[x]=0)or(siz[son[x]]
       
        x2))do dec(j); 93     if not(i>j) then 94     begin 95       y:=b[i]; 96       b[i]:=b[j]; 97       b[j]:=y; 98       inc(i); 99       j:=j-1;100     end;101   until i>j;102   if l
        
         r then110   begin111     tt[i,-1]:=t+1; make(l,(l+r)div 2);112     tt[i,-2]:=t+1; make(((l+r)div 2)+1,r);113   end;114 end;115 begin116   readln(n); m:=(n-1)*2;117   for i:=1 to n-1 do118   begin119     readln(b[i*2-1,1],b[i*2-1,2]);120     b[i*2,1]:=b[i*2-1,2]; b[i*2,2]:=b[i*2-1,1];121   end;122   sort(1,m); j:=1;123   for i:=1 to n do124   begin125     if j>m then break;126     if b[j,1]>i then continue;127     c[i]:=j; while b[j,1]=i do inc(j);128   end;129   dep[1]:=1; fa[1]:=-1; dfs1(1);130   totw:=1; top[1]:=1; tt2[1]:=1; w[1]:=1; flag[1]:=1; dfs2(1);131   t:=0; make(1,n);132   readln(q);133   for i:=1 to q do134   begin135     readln(j,k,l);136     ss(j,k,l);137   end;138 end.