当前位置：网站首页>codevs 2370 Small room tree (LCA)

codevs 2370 Small room tree (LCA)

2022-08-10 11:52:00 【51CTO】

Description

小机房有棵焕狗种的树,树上有N个节点,节点标号为0到N-1,有两只虫子名叫飘狗和大吉狗,分居在两个不同的节点上.有一天,他们想爬到一个节点上去搞基,但是作为两只虫子,他们不想花费太多精力.已知从某个节点爬到其父亲节点要花费 c 的能量（从父亲节点爬到此节点也相同）,他们想找出一条花费精力最短的路,以使得搞基的时候精力旺盛,他们找到你要你设计一个程序来找到这条路,要求你告诉他们最少需要花费多少精力

Input Description

第一行一个n,接下来n-1行每一行有三个整数u,v, c .表示节点 u 爬到节点 v 需要花费 c 的精力.(1<=n<=50000, 1<=m<=75000, 0<=c<=1000)
第n+1行有一个整数m表示有m次询问.接下来m行每一行有两个整数 u ,v 表示两只虫子所在的节点

Output Description

一共有m行,每一行一个整数,表示对于该次询问所得出的最短距离.

Sample Input

Sample Output

思路

LCA 问题,We set a weight for each point tim[i] is equal to the sum of the weights of all edges in the path from the root node to it,So the shortest path weight to be crawled by the bug is tim[u]+tim[v]-2*tim[lca(u,v)] .

采用离线 tarjan 算法可以解决这一问题,The weight of each edge we can store in the child nodes.

However, the disadvantage is that the offline algorithm cannot guarantee that the calculation order is consistent with the input order,So we use a variable to label the sequence number of each query,After all the results are obtained, they are sorted according to the sequence number and output.

AC 代码

       
       #include<iostream>
       
       #include<vector>
       
       #include<cstring>
       
       #include<algorithm>
       
       #include<cstdio>
       
       using 
       
       namespace 
       
       std;
       
       typedef 
       
       pair
       
       <
       
       int,
       
       int
       
       > 
       
       P;
       
       const 
       
       int 
       
       maxn
       
       =
       
       51000;
       
       int 
       
       fa[
       
       maxn];
       
       int 
       
       rk[
       
       maxn];
       
       bool 
       
       visit[
       
       maxn];
       
       int 
       
       tim[
       
       maxn];              
       
       //将 u->v Path weights are stored in  v 中
       
       vector
       
       <
       
       int
       
       > 
       
       tree[
       
       maxn];
       
       vector
       
       <
       
       P
       
       > 
       
       Qes[
       
       maxn];
       
       vector
       
       <
       
       P
       
       > 
       
       ans;
       
       int 
       
       ancestor[
       
       maxn];
       
       struct 
       
       node
       
{
       
       int 
       
       to;
       
       int 
       
       next;
       
       int 
       
       cost;
       
} 
       
       edge[
       
       maxn
       
       <<
       
       1];
       
       int 
       
       head[
       
       maxn
       
       <<
       
       1],
       
       tot;
       
       void 
       
       addedge(
       
       int 
       
       u,
       
       int 
       
       v,
       
       int 
       
       cost)
       
{
       
       edge[
       
       tot].
       
       to
       
       =
       
       v;
       
       edge[
       
       tot].
       
       next
       
       =
       
       head[
       
       u];
       
       edge[
       
       tot].
       
       cost
       
       =
       
       cost;
       
       head[
       
       u]
       
       =
       
       tot
       
       ++;
       
}
       
       void 
       
       init(
       
       int 
       
       n)
       
{
       
       memset(
       
       rk,
       
       0,
       
       sizeof(
       
       rk));
       
       memset(
       
       visit,
       
       false,
       
       sizeof(
       
       visit));
       
       memset(
       
       ancestor,
       
       0,
       
       sizeof(
       
       ancestor));
       
       memset(
       
       tim,
       
       0,
       
       sizeof(
       
       tim));
       
       memset(
       
       head,
       
       -
       
       1,
       
       sizeof(
       
       head));
       
       tot
       
       =
       
       0;
       
       ans.
       
       clear();
       
       for(
       
       int 
       
       i
       
       =
       
       0; 
       
       i
       
       <
       
       n; 
       
       i
       
       ++)
       
    {
       
       fa[
       
       i]
       
       =
       
       i;
       
       tree[
       
       i].
       
       clear();
       
       Qes[
       
       i].
       
       clear();
       
    }
       
}
       
       int 
       
       find_set(
       
       int 
       
       x)     
       
       //并查集 查询+路径压缩
       
{
       
       if(
       
       x
       
       !=
       
       fa[
       
       x])
       
       fa[
       
       x]
       
       =
       
       find_set(
       
       fa[
       
       x]);
       
       return 
       
       fa[
       
       x];
       
}
       
       void 
       
       union_set(
       
       int 
       
       x,
       
       int 
       
       y)     
       
       //并查集 合并
       
{
       
       x
       
       =
       
       find_set(
       
       x);
       
       y
       
       =
       
       find_set(
       
       y);
       
       if(
       
       rk[
       
       x]
       
       >
       
       rk[
       
       y])
       
       fa[
       
       y]
       
       =
       
       x;
       
       else
       
    {
       
       fa[
       
       x]
       
       =
       
       y;
       
       if(
       
       rk[
       
       x]
       
       ==
       
       rk[
       
       y])
       
       rk[
       
       y]
       
       ++;
       
    }
       
}
       
       void 
       
       LCA(
       
       int 
       
       u,
       
       int 
       
       pa,
       
       int 
       
       cost)
       
{
       
       ancestor[
       
       u]
       
       =
       
       u;
       
       tim[
       
       u]
       
       +=
       
       cost
       
       +
       
       tim[
       
       pa];       
       
       // u point weight = 父节point weight + 边权值
       
       for(
       
       int 
       
       i
       
       =
       
       head[
       
       u]; 
       
       i
       
       !=-
       
       1; 
       
       i
       
       =
       
       edge[
       
       i].
       
       next)
       
    {
       
       int 
       
       to
       
       =
       
       edge[
       
       i].
       
       to;
       
       if(
       
       to
       
       ==
       
       pa)
       
       continue;
       
       LCA(
       
       to,
       
       u,
       
       edge[
       
       i].
       
       cost);
       
       union_set(
       
       u,
       
       to);
       
       ancestor[
       
       find_set(
       
       u)]
       
       =
       
       u;
       
    }
       
       visit[
       
       u]
       
       =
       
       true;
       
       int 
       
       len 
       
       = 
       
       Qes[
       
       u].
       
       size();
       
       for(
       
       int 
       
       i
       
       =
       
       0; 
       
       i
       
       <
       
       len; 
       
       i
       
       ++)
       
       if(
       
       visit[
       
       Qes[
       
       u][
       
       i].
       
       second])
       
        {
       
       int 
       
       anc
       
       =
       
       ancestor[
       
       find_set(
       
       Qes[
       
       u][
       
       i].
       
       second)];
       
       ans.
       
       push_back(
       
       P(
       
       Qes[
       
       u][
       
       i].
       
       first,
       
       tim[
       
       u]
       
       +
       
       tim[
       
       Qes[
       
       u][
       
       i].
       
       second]
       
       -
       
       2
       
       *
       
       tim[
       
       anc]));
       
        }
       
}
       
       int 
       
       main()
       
{
       
       ios::sync_with_stdio(
       
       false);
       
       int 
       
       n,
       
       m;
       
       while(
       
       cin
       
       >>
       
       n)
       
    {
       
       init(
       
       n);
       
       for(
       
       int 
       
       i
       
       =
       
       1; 
       
       i
       
       <
       
       n; 
       
       i
       
       ++)
       
        {
       
       int 
       
       u,
       
       v,
       
       cost;
       
       cin
       
       >>
       
       u
       
       >>
       
       v
       
       >>
       
       cost;
       
       addedge(
       
       u,
       
       v,
       
       cost);
       
       addedge(
       
       v,
       
       u,
       
       cost);
       
        }
       
       cin
       
       >>
       
       m;
       
       for(
       
       int 
       
       i
       
       =
       
       0; 
       
       i
       
       <
       
       m; 
       
       i
       
       ++)
       
        {
       
       int 
       
       u,
       
       v;
       
       cin
       
       >>
       
       u
       
       >>
       
       v;
       
       Qes[
       
       u].
       
       push_back(
       
       P(
       
       i,
       
       v));       
       
       //其中 i The serial number that marks its entry
       
       Qes[
       
       v].
       
       push_back(
       
       P(
       
       i,
       
       u));
       
        }
       
       LCA(
       
       0,
       
       -
       
       1,
       
       0);
       
       sort(
       
       ans.
       
       begin(),
       
       ans.
       
       end());        
       
       //因为 tarjan Offline algorithms do not guarantee the same order of computation and input
       
       int 
       
       len
       
       =
       
       ans.
       
       size();
       
       for(
       
       int 
       
       i
       
       =
       
       0; 
       
       i
       
       <
       
       len; 
       
       i
       
       ++)
       
       cout
       
       <<
       
       ans[
       
       i].
       
       second
       
       <<
       
       endl;
       
    }
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.