CODE[VS]4633Mz树链剖分练习

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

1 2

2 3

1 4

2 5

1 4 5

2 1 5

1 1 3

2 5 3

2 4 3

Sample Output

题解：

如题名，数剖练习题。

代码：

 var

   son,siz,dep,top,w,fa,tt2,c,flag:array[-..]of longint;

   tt:array[-..,-..]of longint;

   b:array[-..,..]of longint;

   i,j,k,l,n,m,totw,q,t:longint;

 function cc2(x,l,r:longint):longint;

 begin

   cc2:=; cc2:=cc2+(r-l+)*tt[x,];

   if tt[x,]=tt[x,] then exit;

   if r<=(tt[x,]+tt[x,])div  then cc2:=cc2+cc2(tt[x,-],l,r)else

   if l>(tt[x,]+tt[x,])div  then cc2:=cc2+cc2(tt[x,-],l,r)else

   begin cc2:=cc2+cc2(tt[x,-],l,(tt[x,]+tt[x,])div );

   cc2:=cc2+cc2(tt[x,-],((tt[x,]+tt[x,])div )+,r); end;

 end;

 procedure cc1(x,l,r:longint);

 begin

   if(l=tt[x,])and(r=tt[x,])then

   begin tt[x,]:=tt[x,]+; exit; end;

   if r<=(tt[x,]+tt[x,])div  then cc1(tt[x,-],l,r)else

   if l>(tt[x,]+tt[x,])div  then cc1(tt[x,-],l,r)else

   begin cc1(tt[x,-],l,(tt[x,]+tt[x,])div );

   cc1(tt[x,-],((tt[x,]+tt[x,])div )+,r); end;

 end;

 procedure ss(z,x,y:longint);

 var i,j,k,l,f1,f2,tot:longint;

 begin

   f1:=top[x]; f2:=top[y]; tot:=;

   while f1<>f2 do

   begin

     if dep[f1]<dep[f2] then

     begin j:=f1; f1:=f2; f2:=j; j:=x; x:=y; y:=j; end;

     if z= then cc1(,w[f1],w[x])else

     tot:=tot+cc2(,w[f1],w[x]); x:=fa[f1]; f1:=top[x];

   end;

   if w[x]>w[y] then begin j:=x; x:=y; y:=j; end;

   if z= then cc1(,w[x],w[y])else

   begin tot:=tot+cc2(,w[x],w[y]); writeln(tot); end;

 end;

 procedure dfs2(x:longint);

 var i,j,k,l:longint;

 begin

   j:=c[x];

   while b[j,]=x do

   begin

     if b[j,]=son[x] then

     begin

       flag[b[j,]]:=; top[b[j,]]:=top[x];

       inc(totw); w[b[j,]]:=totw; tt2[totw]:=b[j,];

       dfs2(b[j,]);

     end;

     inc(j);

   end;

   j:=c[x];

   while b[j,]=x do

   begin

     if flag[b[j,]]= then

     begin

       flag[b[j,]]:=; top[b[j,]]:=b[j,];

       inc(totw); w[b[j,]]:=totw; tt2[totw]:=b[j,];

       dfs2(b[j,]);

     end;

     inc(j);

   end;

 end;

 procedure dfs1(x:longint);

 var i,j,k,l:longint;

 begin

   j:=c[x]; siz[x]:=;

   while b[j,]=x do

   begin

     if fa[b[j,]]= then

     begin

       fa[b[j,]]:=x;

       dep[b[j,]]:=dep[x]+;

       dfs1(b[j,]); siz[x]:=siz[x]+siz[b[j,]];

       if(son[x]=)or(siz[son[x]]<siz[b[j,]])then

       son[x]:=b[j,];

     end;

     inc(j);

   end;

 end;

 procedure sort(l,r:longint);

 var

   i,j,x,x2:longint;

   y:array[..]of longint;

 begin

   i:=l; j:=r;

   x:=b[(l+r)div ,];

   x2:=b[(l+r)div ,];

   repeat

     while(b[i,]<x)or((b[i,]=x)and(b[i,]<x2))do inc(i);

     while(x<b[j,])or((b[j,]=x)and(b[j,]>x2))do dec(j);

     if not(i>j) then

     begin

       y:=b[i];

       b[i]:=b[j];

       b[j]:=y;

       inc(i);

       j:=j-;

     end;

   until i>j;

   if l<j then sort(l,j);

   if i<r then sort(i,r);

 end;

 procedure make(l,r:longint);

 var i,j,k:longint;

 begin

   inc(t); i:=t; tt[i,]:=l; tt[i,]:=r;

   if l<>r then

   begin

     tt[i,-]:=t+; make(l,(l+r)div );

     tt[i,-]:=t+; make(((l+r)div )+,r);

   end;

 end;

 begin

   readln(n); m:=(n-)*;

   for i:= to n- do

   begin

     readln(b[i*-,],b[i*-,]);

     b[i*,]:=b[i*-,]; b[i*,]:=b[i*-,];

   end;

   sort(,m); j:=;

   for i:= to n do

   begin

     if j>m then break;

     if b[j,]>i then continue;

     c[i]:=j; while b[j,]=i do inc(j);

   end;

   dep[]:=; fa[]:=-; dfs1();

   totw:=; top[]:=; tt2[]:=; w[]:=; flag[]:=; dfs2();

   t:=; make(,n);

   readln(q);

   for i:= to q do

   begin

     readln(j,k,l);

     ss(j,k,l);

   end;

 end.

巴特西