题目大意:给你一棵树以及相邻节点之间的距离，之后询问2点之间的距离。 用dis数组存根节点到其他节点的距离，则有distance(a,b)=dis[a]+dis[b]-dis[lca(a,b)]*2,所以这题可以用树上倍增求LCA。
#include <cstdio>#include <cstring>#include <vector>#include <algorithm>using namespace std;inline char tc(void){ static char fl[10000+1],*A=fl,*B=fl; return A==B?B=(A=fl)+fread(fl,1,10000,stdin),A==B?EOF:*A++:*A++;}inline void read(int &a){ a=0;static char c; while((c=tc())<'0'||c>'9'); while(c>='0'&&c<='9') a=a*10+c-'0',c=tc(); return ;}struct Edge{ int to,cost; Edge(int a,int b):to(a),cost(b){}};int n,q,deep[1001],x,y,z,dis[1001],fa[1001][12];vector<Edge>s[1001];void dfs(int x){ int now=1; while(deep[x]>(1<<now)) fa[x][now]=fa[fa[x][now-1]][now-1],++now; for (int i=0;i<s[x].size();++i) if(!deep[s[x][i].to]) fa[s[x][i].to][0]=x, dis[s[x][i].to]=dis[x]+s[x][i].cost, deep[s[x][i].to]=deep[x]+1, dfs(s[x][i].to); return ;}int lca(int x,int y){ if(deep[x]>deep[y]) swap(x,y); int k=deep[y]-deep[x]; for (int i=0;i<12;++i) if(k&(1<<i)) y=fa[y][i]; if(x==y) return x; for (int i=11;i>=0;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0];}int main(void){ register int i; read(n),read(q); for(i=1;i<n;++i) read(x),read(y),read(z),s[x].push_back(Edge(y,z)),s[y].push_back(Edge(x,z)); deep[1]=1; dfs(1); for (i=1;i<=q;++i) read(x),read(y),PRintf("%d/n",dis[x]+dis[y]-dis[lca(x,y)]*2); return 0;}新闻热点
疑难解答
