zoj3195(lca / RMQ在线)

题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3195

题意: 给出一棵 n 个节点的带边权的树, 有 q 组形如 x, y, z 的询问, 输出 x, y, z之间的最短路径.

思路: 在纸上画下不难发现 x, y, z之间的最短路径就是 x, y, z 两两之间的最短路径和的一半.

我们可以通过 lca 模板求出 x, y, z 两两之间的最短路径, 然后再算下 x, y, z三点之间的最短路径即可.

这题应该是用 RMQ 在线比较好写一点, 用 tarjan 的话记录路径有点麻烦.

代码:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <math.h>

 using namespace std;

 const int MAXN = 5e4 + ;

 struct node{

     int v, w, next;

 }edge[MAXN << ];

 int dp[MAXN << ][];

 int ver[MAXN << ], deep[MAXN << ], first[MAXN];

 int dis[MAXN], head[MAXN], vis[MAXN], indx, ip;

 inline void init(void){

     memset(vis, , sizeof(vis));

     memset(head, -, sizeof(head));

     indx = ;

     ip = ;

 }

 void addedge(int u, int v, int w){

     edge[ip].v = v;

     edge[ip].w = w;

     edge[ip].next = head[u];

     head[u] = ip++;

 }

 void dfs(int u, int h){

     vis[u] = ;

     ver[++indx] = u;

     deep[indx] = h;

     first[u] = indx;

     for(int i = head[u]; i != -; i = edge[i].next){

         int v = edge[i].v;

         if(!vis[v]){

             dis[v] = dis[u] + edge[i].w;

             dfs(v, h + );

             ver[++indx] = u;

             deep[indx] = h;

         }

     }

 }

 void ST(int n){

     for(int i = ; i <= n; i++){

         dp[i][] = i;

     }

     for(int j = ; ( << j) <= n; j++){

         for(int i = ; i + ( << j) -  <= n; i++){

             int x = dp[i][j - ], y = dp[i + ( << (j - ))][j - ];

             dp[i][j] = deep[x] < deep[y] ? x : y;

         }

     }

 }

 int RMQ(int l, int r){

     int len = log2(r - l + );

     int x = dp[l][len], y = dp[r - ( << len) + ][len];

     return deep[x] < deep[y] ? x : y;

 }

 int LCA(int x, int y){

     int l = first[x], r = first[y];

     if(l > r) swap(l, r);

     int pos = RMQ(l, r);

     return ver[pos];

 }

 int main(void){

     bool flag = false;

     int n, q, x, y, z;

     while(~scanf("%d", &n)){

         if(flag) puts("");

         flag = true;

         init();

         for(int i = ; i < n; i++){

             scanf("%d%d%d", &x, &y, &z);

             addedge(x, y, z);

             addedge(y, x, z);

         }

         dis[] = ;

         dfs(, );

         ST( * n - );

         scanf("%d", &q);

         while(q--){

             scanf("%d%d%d", &x, &y, &z);

             int lca1 = LCA(x, y);

             int lca2 = LCA(x, z);

             int lca3 = LCA(y, z);

             int sol1 = dis[x] + dis[y] -  * dis[lca1];

             int sol2 = dis[x] + dis[z] -  * dis[lca2];

             int sol3 = dis[y] + dis[z] -  * dis[lca3];

             printf("%d\n", (sol1 + sol2 + sol3) >> );

         }

     }

     return ;

 }