求三点的最短路径和,先求出两两之间的路径和,再除以2就是答案,可以把它看作数轴上的三点,另外,这还可以推广到一般情况
由于zoj挂了,暂时放在这里,应该可以过的
2月8日更新:wa了一次,原因是预处理dp数组的第二维开小一倍,本来是re才对,结果返回wa,最讨厌这样子...
#define N 50010 struct edge{ int v; int len; int next; }e[2*N]; int ecnt; int head[N]; bool vis[N]; int n;//点数 int R[N];//第一次出现i点下标 int p[N*2];//记录路径点编号 int dis[N];//与根的距离 int dep[2*N];//深度 int dp[20][2*N];//从j开始长度为2^i路径的最近公共祖先下标,这里这里!!!第二维要2倍大小!! int num; void init(){ memset(head,-1,sizeof(head)); memset(R,-1,sizeof(R)); memset(vis,0,sizeof(vis)); ecnt=0; } void add(int u,int v,int len){ e[ecnt].v = v; e[ecnt].len = len; e[ecnt].next = head[u]; head[u] = ecnt++; e[ecnt].v = u; e[ecnt].len = len; e[ecnt].next = head[v]; head[v] = ecnt++; } void dfs(int u,int depth){ vis[u] = 1; p[++num] = u; dep[num] = depth; for(int i=head[u];i!=-1;i=e[i].next){ int v = e[i].v; if(!vis[v]){ dis[v] = dis[u]+e[i].len; dfs(v,depth+1); p[++num] = u; dep[num] = depth; } } } void init_rmq(){ int i,j; for(i=1;i<=num;i++){ if(R[p[i]] == -1){ R[p[i]] = i; } } for(i=1;i<=num;i++){ dp[0][i] = i; } int t = (int)(log(num*1.0)/log(2.0)); for(i=1;i<=t;i++){ for(j=1;j+(1<<(i-1))<=num;j++){ int a = dp[i-1][j],b = dp[i-1][j+(1<<(i-1))]; if(dep[a]<=dep[b]){ dp[i][j] = a; } else dp[i][j] = b; } } } int rmq(int u,int v){//返回最近公共祖先的编号 if(R[u]>=R[v])swap(u,v); int s = R[u],t = R[v]; int k = (int)(log((t-s+1)*1.0)/log(2.0)); int a = dp[k][s],b = dp[k][t-(1<<k)+1]; if(dep[a]<=dep[b])return p[a]; else return p[b]; } int main(){ bool ok=0; while(scanf("%d",&n) != -1){ if(ok)puts(""); ok=1; int i,j; init(); for(i=1;i<n;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); } num = 0; dis[0] = 0; dep[0] = 0; dfs(0,0); init_rmq(); int m ; scanf("%d",&m); while(m--){ int a,b,c; scanf("%d%d%d",&a,&b,&c); int fa; int len; int ans = 0; fa = rmq(a,b); len = dis[a]+dis[b]-2*dis[fa]; ans+=len; fa = rmq(a,c); len = dis[a]+dis[c]-2*dis[fa]; ans+=len; fa = rmq(b,c); len = dis[b]+dis[c]-2*dis[fa]; ans+=len; printf("%d\n",ans/2); } } return 0; }