How far away ？
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 11739 Accepted Submission(s): 4325
Problem Description
There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this "How far is it if I want to go from house A to house B"? Usually it hard to answer. But luckily int this village the answer is always unique, since the roads are built in the way that there is a unique simple path("simple" means you can't visit a place twice) between every two houses. Yout task is to answer all these curious people.
Input
First line is a single integer T(T<=10), indicating the number of test cases.
For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n.
Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.
For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n.
Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.
Output
For each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.
Sample Input
2 3 2 1 2 10 3 1 15 1 2 2 3 2 2 1 2 100 1 2 2 1
Sample Output
10 25 100 100
题意:
n个点组成的一棵树，2点之间有长度。m次查询，问x到y上每个点只能走一次的最近的距离是多少。
思路:
是一棵树，又x到y的路径上每个点只能走一次，dfs时记录当前节点到根的距离，然后对于查询x,y,求出lca(x,y),答案就是dis[x] + dis[y] - 2 * dis[lca(x,y)];
/* * Author: sweat123 * Created Time: 2016/7/13 8:53:48 * File Name: main.cpp */ #include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<string> #include<vector> #include<cstdio> #include<time.h> #include<cstring> #include<iostream> #include<algorithm> #define INF 1<<30 #define MOD 1000000007 #define ll long long #define lson l,m,rt<<1 #define key_value ch[ch[root][1]][0] #define rson m+1,r,rt<<1|1 #define pi acos(-1.0) using namespace std; const int MAXN = 40010; struct node{ int to; int val; int next; }edge[MAXN*2]; int dp[MAXN*2][20],n,m,ind,pre[MAXN],vis[MAXN]; int dfn[MAXN*2],first[MAXN],ver[MAXN*2],tot; ll dis[MAXN]; //dfn 表示深度 first第一次出现这个点的下标 dis长度 ver先序访问的节点编号 tot编号个数 void add(int x,int y,int z){ edge[ind].to = y; edge[ind].val = z; edge[ind].next = pre[x]; pre[x] = ind ++; } void dfs(int rt,int dep){ vis[rt] = 1; ver[++tot] = rt; dfn[tot] = dep; first[rt] = tot; for(int i = pre[rt]; i != -1; i = edge[i].next){ int t = edge[i].to; if(!vis[t]){ dis[t] = dis[rt] + edge[i].val; dfs(t,dep+1); ver[++tot] = rt;//先序访问 dfn[tot] = dep; } } } void rmq(){ for(int i = 1; i <= tot; i++){ dp[i][0] = i; } for(int i = 1; i < 20; i++){ for(int j = 1; j + (1 << i) - 1 <= tot; j++){ if(dfn[dp[j][i-1]] > dfn[dp[j+(1<<(i-1))][i-1]]){ dp[j][i] = dp[j+(1<<(i-1))][i-1]; } else { dp[j][i] = dp[j][i-1]; } } } } int askrmq(int x,int y){ x = first[x]; y = first[y]; if(x > y)swap(x,y); int k = (int)(log(y - x + 1) * 1.0 / log(2.0)); int l = dp[x][k]; int r = dp[y-(1<<k)+1][k]; if(dfn[l] > dfn[r])return r; else return l; } int main(){ int t,flag = 0; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); ind = 0; tot = 0; memset(vis,0,sizeof(vis)); memset(dis,0,sizeof(dis)); memset(pre,-1,sizeof(pre)); for(int i = 1; i < n; i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z),add(y,x,z); } dfs(1,1); rmq(); if(flag)puts(""); flag = 1; while(m--){ int x,y; scanf("%d%d",&x,&y); int tp = ver[askrmq(x,y)]; ll ans = dis[x] - dis[tp] + dis[y] - dis[tp]; printf("%lld ",ans); } } return 0; }