好吧，这题很有意思。。
第一眼撇的时候还以为是（SPFA）呜。。。。
然后发现要Q次询问就想到了LCA
但是发现不是求LCA。。
于是想到了一个神奇的定律：
两点的LCA一定在u到v的最短路上。。
并且也一定在两点与根节点的路上。
所以用dis[a]+dis[b]-2*dis[LCA(a,b)]就得到答案啦！
这道题有一个坑点！注意！
我们先来看一个测试：
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int main(){ int x,y; scanf("%d%d",&x,&y); int k1=(int)(log(y-x+1.0)/log(2.0)); int k2=0; while(1<<(k2+1)<=y-x+1)k2++; printf("%d %d",k1,k2); }
这看起来是等价的。。但是。。
输入：1 8
输出：2 3
恩，你没有看错，就是2、3.
事实是这样的：C++ 计算log(8)/log(2)时，得到的答案为（double）2.9999996。
强制转换为int后，变成了2；
但是这样就可以了QAQ
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int main(){ int num; int num2; double k=log(8.0)/log(2.0); num2=k; printf("%d",num2); }
恩，这样就是啦awa
万恶的C++。。。
下面贴代码
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> using namespace std; struct data{ int to,next,value; }g[5000]; int head[1001]; bool qs[1001]; int id[1001]; int vs[5000]; int depth[5000]; int dp[5000][20]; int dd[1001]; int dfs_clock=1; int n,q,num=0,root; void ins(int a,int b,int v){ g[++num].next=head[a]; head[a]=num; g[num].to=b; g[num].value=v; } void dfs(int u,int fa,int d){ id[u]=dfs_clock; vs[dfs_clock]=u; depth[dfs_clock++]=d; for(int i=head[u];i;i=g[i].next) { int v=g[i].to; if(v==fa) continue; dd[v]=dd[u]+g[i].value; dfs(v,u,d+1); vs[dfs_clock]=u; depth[dfs_clock++]=d; } } void RMQ(int nn){ for(int i=1;i<=nn;i++) dp[i][0]=i; for(int j=1;(1<<j)<=nn;j++) for(int i=1;i+(1<<j)-1<=nn;i++) { int a=dp[i][j-1]; int b=dp[i+(1<<(j-1))][j-1]; if(depth[a]<=depth[b]) dp[i][j]=a; else dp[i][j]=b; } } int cal(int x,int y){ double k2=log(y-x+1.0)/log(2.0); int k=k2; int a=dp[x][k]; int b=dp[y-(1<<k)+1][k]; if(depth[a]<=depth[b]) return a; else return b; } int lca(int u,int v){ int x=id[u]; int y=id[v]; if(x<y) return vs[cal(x,y)]; else return vs[cal(y,x)]; } int main(){ scanf("%d%d",&n,&q); for(int i=1;i<n;i++) { int a,b,v; scanf("%d%d%d",&a,&b,&v); qs[b]=1; ins(a,b,v);ins(b,a,v); } dfs(1,0,0); RMQ(dfs_clock-1); for(int i=1;i<=q;i++) { int a,b; scanf("%d%d",&a,&b); printf("%d ",dd[a]+dd[b]-2*dd[lca(a,b)]); } }
不会RMQ的可以看我的传送门
当然，要打树上倍增的也是可以啦。。
代码就不贴了。
真是奇特的题目233~