﻿ Contest1389 - 2018年第三阶段个人训练赛第四场. Transit Tree Path（DFS） - bet365体育app下载_外围bet365 网址_bet365娱乐在线先锋网 bet365体育app下载_外围bet365 网址_bet365娱乐在线

# bet365体育app下载_外围bet365 网址_bet365娱乐在线先锋网?bet365体育app下载_外围bet365 网址_bet365娱乐在线片段及技术文章聚合

## Contest1389 - 2018年第三阶段个人训练赛第四场. Transit Tree Path（DFS）

### 问题 D: Transit Tree Path

[提交] [状态] [讨论版] [命题人:admin]

You are given a tree with N vertices.
Here, a tree is a kind of graph, and more specifically, a connected undirected graph with N?1 edges, where N is the number of its vertices.
The i-th edge (1≤i≤N?1) connects Vertices ai and bi, and has a length of ci.

You are also given Q queries and an integer K. In the j-th query (1≤j≤Q):

find the length of the shortest path from Vertex xj and Vertex yj via Vertex K.
Constraints
3≤N≤105
1≤ai,bi≤N(1≤i≤N?1)
1≤ci≤109(1≤i≤N?1)
The given graph is a tree.
1≤Q≤105
1≤K≤N
1≤xj,yj≤N(1≤j≤Q)
xj≠yj(1≤j≤Q)
xj≠K,yj≠K(1≤j≤Q)

?

Input is given from Standard Input in the following format:
N??
a1 b1 c1??
:??
aN?1?bN?1?cN?1
Q K
x1 y1
:??
xQ yQ

?

?

Print the responses to the queries in Q lines.
In the j-th line j(1≤j≤Q), print the response to the j-th query.

?

```5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5
```

?

```3
2
4
```

?

The shortest paths for the three queries are as follows:
Query 1: Vertex 2 → Vertex 1 → Vertex 2 → Vertex 4 : Length 1+1+1=3
Query 2: Vertex 2 → Vertex 1 → Vertex 3 : Length 1+1=2
Query 3: Vertex 4 → Vertex 2 → Vertex 1 → Vertex 3 → Vertex 5 : Length 1+1+1+1=4

``````
#include
#include
using namespace std;
long long dist[100005];
vector<> > G[100005];
int N,a,b,c,Q,K;
int dfs(int nod)
{
for(auto it:G[nod])
{
if(!dist[it.first]){
dist[it.first]=dist[nod]+it.second;
dfs(it.first);
}
}
}
int main()
{
cin>>N;
for(int i=1; i>a>>b>>c;
G[a].push_back({b,c});
G[b].push_back({a,c});
}
cin>>Q>>K;
dist[K]=1;
dfs(K);
while(Q--)
{
cin>>a>>b;
cout<``````

?