学步园

题目大意：

      给你一个无根树，要求满足两个操作：

      1.查询两个点的距离；

      2.修改某一条边的权值。

正确做法是用线段树维护一个DFS序列，因为想温习下动态树所以很NC的编了个动态树。

较之之前的动态树，这里多得操作是查询两个点的距离。

由于死循环TLE了1次之后AC。

很无解的，常数巨大的动态树竟然也可以超过绝大多数的线段树：

program poj2763; const maxn=100000;<br /> var<br /> next,p,c:array[0..2*maxn] of longint;<br /> l,r,fa,w,s,d,e:array[0..maxn] of longint;<br /> root:array[0..maxn] of boolean;<br /> i,j,k,a,b,t,n,q,ss,cc,tmp:longint;</p> <p>procedure left(i:longint);<br /> begin<br /> j:=r[i];r[i]:=l[j];fa[r[i]]:=i;;l[j]:=i;<br /> fa[j]:=fa[i];fa[i]:=j;<br /> root[j]:=root[i];root[i]:=false;<br /> s[i]:=s[l[i]]+s[r[i]]+w[i];<br /> s[j]:=s[l[j]]+s[r[j]]+w[j];<br /> if i=l[fa[j]] then l[fa[j]]:=j else<br /> if i=r[fa[j]] then r[fa[j]]:=j;<br /> i:=j;<br /> end;</p> <p>procedure right(i:longint);<br /> begin<br /> j:=l[i];l[i]:=r[j];fa[l[i]]:=i;r[j]:=i;<br /> fa[j]:=fa[i];fa[i]:=j;<br /> root[j]:=root[i];root[i]:=false;<br /> s[i]:=s[l[i]]+s[r[i]]+w[i];<br /> s[j]:=s[l[j]]+s[r[j]]+w[j];<br /> if i=l[fa[j]] then l[fa[j]]:=j else<br /> if i=r[fa[j]] then r[fa[j]]:=j;<br /> i:=j;<br /> end;</p> <p>procedure cut(i:longint);<br /> begin<br /> while not root[i] do<br /> if l[fa[i]]=i then right(fa[i]) else left(fa[i]);<br /> tmp:=s[l[i]];root[l[i]]:=true;<br /> dec(s[i],tmp);l[i]:=0;<br /> end;</p> <p>procedure access(i:longint);<br /> begin<br /> cut(i);<br /> while fa[i]<>0 do begin<br /> cut(fa[i]);root[fa[i]]:=false;<br /> inc(tmp,s[i]);<br /> fa[r[i]]:=fa[i];j:=fa[i];<br /> l[fa[i]]:=r[i];r[i]:=fa[i];<br /> fa[i]:=fa[j];fa[j]:=i;<br /> s[j]:=s[l[j]]+s[r[j]]+w[j];<br /> s[i]:=s[l[i]]+s[r[i]]+w[i];<br /> end;<br /> end;</p> <p>procedure link(a,b,cc:longint);<br /> begin inc(t);next[t]:=d[a];d[a]:=t;p[t]:=b;c[t]:=cc end;</p> <p>procedure dfs(i,f:longint);var k:longint;<br /> begin<br /> root[i]:=true;fa[i]:=f;k:=d[i];<br /> while k<>0 do begin<br /> if p[k]<>f then begin<br /> w[p[k]]:=c[k];s[p[k]]:=c[k];<br /> dfs(p[k],i);e[(k+1)div 2]:=p[k];<br /> end;<br /> k:=next[k];<br /> end;<br /> end;</p> <p>begin<br /> readln(n,q,ss);<br /> for i:=1 to n-1 do begin<br /> readln(a,b,cc);<br /> link(a,b,cc);link(b,a,cc);<br /> end;<br /> dfs(ss,0);<br /> for i:=1 to q do begin<br /> read(a);<br /> if a=1 then begin<br /> readln(b,cc);j:=e[b];<br /> cut(j);inc(s[j],cc-w[j]);w[j]:=cc;<br /> end else begin<br /> readln(b);<br /> access(ss);access(b);<br /> ss:=b;writeln(tmp);<br /> end;<br /> end;<br /> end.