在一棵树上 求2个点的最短距离。那么首先利用LCA找到2个点的近期公共祖先
公式：ans = dis(x) + dis(y) - 2 * dis(lca(x,y))
这里的dis(x)指的上x距离根节点的距离
注意一些细节方面，比方数组的越界问题：
#include#include #include #include using namespace std;typedef long long LL;const int maxn = 45555;struct Edge{ int to; LL dist; Edge(int to,LL dist):to(to),dist(dist){};};int n,m;int deep[maxn],pa[maxn][22];LL dis[maxn];vector G[maxn];void init(){ memset(pa,-1,sizeof(pa)); for(int i = 1; i <= n; i++) G[i].clear();}//----------------LAC---------------------------void dfs(int pos,int d,LL dist){ //printf("[%d %d]\n",pos,dist); deep[pos] = d; dis[pos] = dist; int Size = G[pos].size(); for(int i = 0; i < Size; i++) dfs(G[pos][i].to,d + 1,dist + G[pos][i].dist);}void lca_init(){ for(int j = 1; (1 << j) <= n; j++) for(int i = 1; i <= n; i++) if(pa[i][j - 1] != -1) pa[i][j] = pa[pa[i][j - 1]][j - 1];}int lca(int a,int b){ if(a == b) return a; if(deep[a] < deep[b]) swap(a,b); int i; for(i = 0;(1 << i) <= deep[a]; i++); for(int j = i; j >= 0; j--) if(pa[a][j] != -1 && deep[pa[a][j]] >= deep[b]) a = pa[a][j]; if(a == b) return b; for(int j = i; j >= 0; j--) if(pa[a][j] != -1 && deep[pa[a][j]] != deep[pa[b][j]]){ a = pa[a][j]; b = pa[b][j]; } return pa[a][0];}//-------------------------------------------------int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); int x,y,z; init(); for(int i = 0; i < n - 1; i++){ scanf("%d%d%d",&x,&y,&z); G[x].push_back(Edge(y,z)); pa[y][0] = x; } for(int i = 1; i <= n; i++)if(pa[i][0] == -1){ dfs(i,0,0); break; } lca_init(); for(int i = 0; i < m; i++){ scanf("%d%d",&x,&y); LL ans = dis[x] + dis[y] - 2 * dis[lca(x,y)]; printf("%I64d\n",ans); } } return 0;}