SPOJ/QTREE.pas

   1 const
   2   maxn=20100;
   3
   4 var
   5   n,tot,edge_tot,p,q,t,i:longint;
   6   dep,top,father,son,w,size,ehead:array [0..maxn] of longint;
   7   edge:array [0..maxn*2] of record
   8                               adj,next:longint;
   9                             end;
  10   tree:array [0..maxn*4] of longint;
  11   data:array [0..maxn] of record
  12                             x,y,v:longint;
  13                           end;
  14   order,ch:char;
  15
  16 //Implementation of Segment Tree
  17
  18 function max(p,q:longint):longint;
  19 begin
  20   if p>q then exit(p) else exit(q);
  21 end;
  22
  23 procedure update(root:longint);
  24 begin
  25   tree[root]:=max(tree[root*2],tree[root*2+1]);
  26 end;
  27
  28 procedure tree_ins(l,r,pos,v,root:longint);
  29 var
  30   m:longint;
  31
  32 begin
  33   if l=r then
  34     begin
  35       tree[root]:=v;
  36       exit;
  37     end;
  38   m:=(l+r) shr 1;
  39   if pos<=m then tree_ins(l,m,pos,v,root*2) else
  40     tree_ins(m+1,r,pos,v,root*2+1);
  41   update(root);
  42 end;
  43
  44 function tree_query(l,r,p,q,root:longint):longint;
  45 var
  46   m,t:longint;
  47
  48 begin
  49   if (p<=l) and (r<=q) then exit(tree[root]);
  50   m:=(l+r) shr 1;
  51   t:=0;
  52   if p<=m then t:=max(t,tree_query(l,m,p,q,root*2));
  53   if q>m then t:=max(t,tree_query(m+1,r,p,q,root*2+1));
  54   exit(t);
  55 end;
  56
  57 //End of Segment Tree
  58
  59 procedure insedge(x,y:longint);
  60 begin
  61   inc(edge_tot);
  62   edge[edge_tot].adj:=y;
  63   edge[edge_tot].next:=ehead[x];
  64   ehead[x]:=edge_tot;
  65 end;
  66
  67 procedure dfs(root:longint);
  68 //solve father,dep,size,son
  69 var
  70   now:longint;
  71
  72 begin
  73   size[root]:=1;
  74   son[root]:=0;
  75   now:=ehead[root];
  76   while now<>-1 do
  77     begin
  78       if edge[now].adj<>father[root] then
  79         begin
  80           father[edge[now].adj]:=root;
  81           dep[edge[now].adj]:=dep[root]+1;
  82           dfs(edge[now].adj);
  83           inc(size[root],size[edge[now].adj]);
  84           if size[son[root]]<size[edge[now].adj] then son[root]:=edge[now].adj;
  85         end;
  86       now:=edge[now].next;
  87     end;
  88 end;
  89
  90 procedure split(root,tp:longint);
  91 //solve top,w
  92 var
  93   now:longint;
  94
  95 begin
  96   inc(tot);
  97   w[root]:=tot;
  98   top[root]:=tp;
  99   if son[root]>0 then split(son[root],top[root]);
 100   now:=ehead[root];
 101   while now<>-1 do
 102     begin
 103       if (edge[now].adj<>father[root]) and (edge[now].adj<>son[root]) then
 104         split(edge[now].adj,edge[now].adj);
 105       now:=edge[now].next;
 106     end;
 107 end;
 108
 109 procedure swap(var p,q:longint);
 110 var
 111   t:longint;
 112
 113 begin
 114   t:=p;
 115   p:=q;
 116   q:=t;
 117 end;
 118
 119 function find(p,q:longint):longint;
 120 var
 121   t1,t2,tmp:longint;
 122
 123 begin
 124   t1:=top[p];
 125   t2:=top[q];
 126   tmp:=0;
 127   while t1<>t2 do
 128     begin
 129       if dep[t1]<dep[t2] then
 130         begin
 131           swap(t1,t2);
 132           swap(p,q);
 133         end;
 134       tmp:=max(tmp,tree_query(1,tot,w[t1],w[p],1));
 135       p:=father[t1];
 136       t1:=top[p];
 137     end;
 138   if p=q then exit(tmp);
 139   if dep[p]>dep[q] then swap(p,q);
 140   exit(max(tmp,tree_query(1,tot,w[son[p]],w[q],1)));
 141 end;
 142
 143 begin
 144   readln(t);
 145   repeat
 146     dec(t);
 147     readln(n);
 148     edge_tot:=0;
 149     fillchar(ehead,sizeof(ehead),255);
 150     fillchar(tree,sizeof(tree),0);
 151     for i:=1 to n-1 do
 152       begin
 153         readln(data[i].x,data[i].y,data[i].v);
 154         insedge(data[i].x,data[i].y);
 155         insedge(data[i].y,data[i].x);
 156       end;
 157     dep[1]:=0;
 158     father[1]:=0;
 159     dfs(1);
 160     tot:=0;
 161     split(1,1);
 162     for i:=1 to n-1 do
 163       begin
 164         if dep[data[i].x]>dep[data[i].y] then swap(data[i].x,data[i].y);
 165         tree_ins(1,tot,w[data[i].y],data[i].v,1);
 166       end;
 167     read(order);
 168     while order<>'D' do
 169       begin
 170         repeat read(ch); until ch=' ';
 171         readln(p,q);
 172         if order='Q' then writeln(find(p,q)) else
 173           tree_ins(1,tot,w[data[p].y],q,1);
 174         read(order);
 175       end;
 176     repeat read(ch); until (ch=#10) or (ch=#13);
 177   until t=0;
 178 end.