【SPOJ

http://acm.hust.edu.cn/vjudge/problem/19960

题意：

有一棵N个节点的树（1<=N<=10000），N-1条边，边的编号为1~N-1，每条边有一个权值，要求模拟两种操作：

1：DIST a b :求点a到点b之间的距离

2：KTH a b k :求从a出发到b遇到的第k个节点的编号

QTREE系列的第二题。求dist就不用说啦，主要是求第k个。

方法一：我是先跳了一遍，求出x到y的距离l，然后用树链剖分的跳法x走了k或者y走了l-k找到该点。很多细节。。。

方法二：先跳一遍，找到lca，然后判断k在x到lca的路上还是y到lca的路上,即是x到lca的第k个点或y到lca的第k‘个点。然后用倍增找到该点。（我觉得这个是最优的）

方法三：跳一遍找到lca后一层一层往上跳。。为什么这个方法不会超时。。TAT

方法一

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 using namespace std;
  7 
  8 const int N=10010;
  9 char s[10];
 10 struct trnode{
 11     int lc,rc,l,r,c;
 12 }t[2*N];
 13 struct node{
 14     int x,y,d,next;
 15 }a[2*N],b[N];
 16 int n,tl,z,len;
 17 int first[N],tot[N],son[N],fa[N],dep[N],ys[N],yss[N],top[N];
 18 
 19 int maxx(int x,int y){return x>y ? x:y;}
 20 
 21 void ins(int x,int y,int d)
 22 {
 23     len++;
 24     a[len].x=x;a[len].y=y;a[len].d=d;
 25     a[len].next=first[x];first[x]=len;
 26 }
 27 
 28 int build_tree(int l,int r)
 29 {
 30     int x=++tl;
 31     t[x].l=l;t[x].r=r;t[x].c=0;
 32     t[x].lc=t[x].rc=-1;
 33     if(l<r)
 34     {
 35         int mid=(l+r)>>1;
 36         t[x].lc=build_tree(l,mid);
 37         t[x].rc=build_tree(mid+1,r);
 38     }
 39     return x;
 40 }
 41 
 42 void change(int x,int p,int c)
 43 {
 44     if(t[x].l==t[x].r) {t[x].c+=c;return;}
 45     int lc=t[x].lc,rc=t[x].rc,mid=(t[x].l+t[x].r)>>1;
 46     if(p<=mid) change(lc,p,c);
 47     else change(rc,p,c);
 48     t[x].c=t[lc].c+t[rc].c;
 49 }
 50 
 51 int query(int x,int l,int r)
 52 {
 53     if(t[x].l==l && t[x].r==r) return t[x].c;
 54     int lc=t[x].lc,rc=t[x].rc,mid=(t[x].l+t[x].r)>>1;
 55     if(r<=mid) return query(lc,l,r);
 56     else if(l>mid) return query(rc,l,r);
 57     return query(lc,l,mid)+query(rc,mid+1,r);
 58 }
 59 
 60 void dfs1(int x)
 61 {
 62     tot[x]=1;son[x]=0;
 63     for(int i=first[x];i;i=a[i].next)
 64     {
 65         int y=a[i].y;
 66         if(y==fa[x]) continue;
 67         fa[y]=x;
 68         dep[y]=dep[x]+1;
 69         dfs1(y);
 70         if(tot[son[x]]<tot[y]) son[x]=y;
 71         tot[x]+=tot[y];
 72     }
 73 }
 74 
 75 void dfs2(int x,int tp)
 76 {
 77     ys[x]=++z;yss[z]=x;top[x]=tp;
 78     if(son[x]) dfs2(son[x],tp);
 79     for(int i=first[x];i;i=a[i].next)
 80     {
 81         int y=a[i].y;
 82         if(y==fa[x] || y==son[x]) continue;
 83         dfs2(y,y);
 84     }
 85 }
 86 
 87 int solve(int x,int y,int k)
 88 {
 89     int tx=top[x],ty=top[y];
 90     int ans=0,l=0,xx=x,yy=y;
 91     bool bk=0;
 92     while(tx!=ty)
 93     {
 94         if(dep[tx]>dep[ty]) swap(tx,ty),swap(x,y);
 95         if(!k) ans+=query(1,ys[ty],ys[y]);
 96         else l+=ys[y]-ys[ty]+1;
 97         y=fa[ty];ty=top[y];
 98     }
 99     
100     if(x==y) {l++;if(!k) return ans;}
101     else 
102     {
103         if(dep[x]>dep[y]) swap(x,y);
104         l+=ys[y]-ys[x]+1;
105         if(!k) return ans+query(1,ys[son[x]],ys[y]);
106     }
107 //找第k个  debug！注意细节！
108     if(k>l) return 0;
109     x=xx,y=yy;tx=top[x],ty=top[y];
110     int now1=1,now2=1,p=0;
111     if(now1==k) return x;
112     if(now2==l-k+1) return y;
113     while(tx!=ty)
114     {
115         if(dep[tx]>dep[ty]) swap(tx,ty),swap(x,y),p=1-p;
116         int ll=ys[y]-ys[ty];
117         if(p)
118         {
119             if(now1+ll>=k) return ans=yss[ys[y]-(k-now1)];
120             else now1+=ll;
121             now1++;if(now1==k) return ans=fa[ty];
122         }
123         else
124         {
125             if(now2+ll>=l-k+1) return ans=yss[ys[y]-(l-k+1-now2)];
126             else now2+=ll;
127             now2++;if(now2==l-k+1) return ans=fa[ty];
128         }
129         y=fa[ty];ty=top[y];
130     }
131     if(dep[x]>dep[y]) swap(x,y),p=1-p;
132     if(p) ans=yss[ys[y]-(k-now1)];
133     else ans=yss[ys[y]-(l-k+1-now2)];
134     return ans;
135 }
136 
137 int main()
138 {
139     freopen("a.in","r",stdin);
140     // freopen("me.out","w",stdout);
141     int T;
142     scanf("%d",&T);
143     while(T--)
144     {
145         scanf("%d",&n);
146         len=0;tl=0;z=0;dep[1]=0;tot[0]=0;
147         memset(fa,0,sizeof(fa));
148         memset(first,0,sizeof(first));
149         for(int i=1;i<n;i++)
150         {
151             scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].d);
152             ins(b[i].x,b[i].y,b[i].d);
153             ins(b[i].y,b[i].x,b[i].d);
154         }
155         dfs1(1);
156         dfs2(1,1);
157         build_tree(1,z);
158         for(int i=1;i<n;i++) if(dep[b[i].x]>dep[b[i].y]) swap(b[i].x,b[i].y);
159         for(int i=1;i<n;i++) change(1,ys[b[i].y],b[i].d);
160         while(1)
161         {
162             scanf("%s",s);
163             int x,y,k=0;
164             if((s[0]=='D' && s[1]=='I') || s[0]=='K') 
165             {
166                 scanf("%d%d",&x,&y);
167                 if(s[0]=='K') scanf("%d",&k);
168                 printf("%d
",solve(x,y,k));
169             }
170             if(s[0]=='D' && s[1]=='O') break;
171         }
172     }
173     return 0;
174 }

方法三

  1 #include<cstdio>
  2 #include<cstring>
  3 #define maxn 11000
  4 using namespace std;
  5 struct enode{int x,y,next;}a[maxn*2];int len,last[maxn];
  6 void ins(int x,int y)
  7 {
  8     len++; a[len].x=x; a[len].y=y;
  9     a[len].next=last[x]; last[x]=len;
 10 }
 11 struct trnode{int lc,rc,l,r,c;}tr[maxn*2];int trlen;
 12 void bt(int l,int r)
 13 {
 14     int now=++trlen;
 15     tr[now].l=l; tr[now].r=r;tr[now].lc=tr[now].rc=-1;
 16     tr[now].c=0;
 17     if(l<r)
 18     {
 19         int mid=(l+r)/2;
 20         tr[now].lc=trlen+1; bt(l,mid);
 21         tr[now].rc=trlen+1; bt(mid+1,r);
 22     }
 23 }
 24 int n,fa[maxn],dep[maxn], son[maxn],tot[maxn],top[maxn];
 25 void pre_tree_node(int x)
 26 {
 27     tot[x]=1;son[x]=0;
 28     for(int k=last[x];k;k=a[k].next)
 29     {
 30         int y=a[k].y;
 31         if(y!=fa[x])
 32         {
 33             fa[y]=x;
 34 dep[y]=dep[x]+1;
 35             pre_tree_node(y);
 36             tot[x]+=tot[y];
 37             if(tot[son[x]]<tot[y]) son[x]=y;
 38         }
 39     }
 40 }
 41 
 42 int z,ys[maxn];
 43 void pre_tree_edge(int x,int tp)
 44 {
 45     ys[x]=++z;top[x]=tp;
 46     if(son[x]!=0)pre_tree_edge(son[x],tp);
 47     for(int k=last[x];k;k=a[k].next)
 48     {
 49         int y=a[k].y;
 50         if(y!=fa[x]&& y!=son[x]) pre_tree_edge(y,y);
 51     }
 52 }
 53 
 54 void change(int now,int p,int c)
 55 {
 56     if( tr[now].l==tr[now].r) { tr[now].c=c; return ;}
 57     int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;
 58     if(p<=mid) change(lc,p,c);  else change(rc,p,c);
 59     tr[now].c=tr[lc].c+tr[rc].c;
 60 }
 61 int  findsum(int now,int l,int r)//findsum的功能就是求新编号为l的边到新编号为r的边的总和（连续）
 62 {
 63     if( l==tr[now].l && tr[now].r==r) return tr[now].c;
 64     int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;
 65     if(mid<l)       return findsum(rc,l,r);
 66     else if(r<=mid) return findsum(lc,l,r);
 67     else            return findsum(lc,l,mid)+findsum(rc,mid+1,r);
 68 }
 69 
 70 
 71 int  solve(int x,int y)
 72 {
 73     int tx=top[x],ty=top[y],ans=0;
 74     while(tx!=ty)
 75     {
 76         if(dep[tx]>dep[ty]){ int t=tx;tx=ty;ty=t; t=x;x=y;y=t;}
 77         ans+= findsum(1,ys[ty],ys[y]);
 78         y=fa[ty];ty=top[y];
 79     }
 80     if(x==y) return ans;
 81     else
 82     {
 83         if(dep[x]>dep[y]){ int t=x;x=y;y=t;}
 84         return ans+ findsum(1,ys[son[x]],ys[y]);
 85     }
 86 }
 87 
 88 int listx[maxn],listy[maxn];   //x一层层往上跳，经过的点保存在listx数组中
 89                                //y一层层往上跳，经过的点保存在listy数组中
 90 int  findKth(int x,int y,int K)//求从x点出发到y点，一路上遇到的第K个点是谁
 91 { //总体思路就是x和y一层层往上跳，比solve好理解啊。
 92     int lx=0,ly=0,fx,fy;
 93     while(x!=y)//如果x和y没有相遇
 94     {
 95         if(dep[x]>dep[y]){ listx[++lx]=x;x=fa[x];}//这里决定谁往上跳，为什么是不比tx和ty？
 96         else { listy[++ly]=y;y=fa[y];}
 97         
 98         if(lx==K) return listx[lx];  //如果提前遇到第K个就直接结束了
 99     }
100     listx[++lx]=x; // 此时x==y，随便listx或者listy都可以保存
101     
102     if(K<=lx)  return listx[K];
103     else       return listy[ ly - (K-lx)+1  ];
104 }
105 struct bian{int x,y,c;}e[maxn];
106 int main()
107 {
108     int i,tt,x,y,c,p,K; scanf("%d",&tt);
109     while(tt--)
110     {
111         scanf("%d",&n);
112         len=0;memset(last,0,sizeof(last));
113         for(i=1;i<n;i++)
114         {
115             scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].c);
116             ins(e[i].x,e[i].y);
117             ins(e[i].y,e[i].x);
118         }
119         
120         dep[1]=fa[1]=0; pre_tree_node(1);
121         
122         z=0; pre_tree_edge(1,1);
123         
124         trlen=0;bt(1,z);
125         
126         for(i=1;i<n;i++)    if( dep[e[i].x]>dep[e[i].y]){ int t=e[i].x;e[i].x=e[i].y;e[i].y=t;}
127         for(i=1;i<n;i++)    change(1,ys[ e[i].y ], e[i].c);
128         
129         char ss[20];
130         while( scanf("%s",ss)!=EOF)
131         {
132             if(ss[1]=='O') break;
133             if(ss[1]=='I'){scanf("%d%d",&x,&y); printf("%d
",solve(x,y));}
134              else{ scanf("%d%d%d",&x,&y,&K); printf("%d
",findKth(x,y,K));}
135         }
136         
137     }
138     return 0;
139 }