lca裸题
#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <queue> #include <map> #include <cmath> #include <iostream> #define INF 0x3f3f3f3f using namespace std; const int N=40005; vector< pair<int,int> > edge[N]; vector<int> que[N],num[N]; int vis[N],f[N],ans[N],dis[N]; int _find(int x) { if(f[x]!=x) return f[x]=_find(f[x]); return f[x]; } void dfs(int u,int pre) { f[u]=u; int up=edge[u].size(); for(int i=0; i<up; i++) { int v=edge[u][i].first,w=edge[u][i].second; if(v==pre) continue; dis[v]=dis[u]+w; dfs(v,u); f[v]=u; } vis[u]=1; up=que[u].size(); for(int i=0; i<up; i++) { int v=que[u][i]; if(vis[v]) ans[num[u][i]]=dis[u]+dis[v]-2*dis[_find(v)]; } } int main() { int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { edge[i].clear(); vis[i]=0; dis[i]=0; que[i].clear(); num[i].clear(); } for(int i=0; i<n-1; i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); edge[u].push_back(make_pair(v,w)); edge[v].push_back(make_pair(u,w)); } for(int i=0; i<m; i++) { int u,v; scanf("%d%d",&u,&v); que[u].push_back(v); que[v].push_back(u); num[u].push_back(i); num[v].push_back(i); } dfs(1,0); for(int i=0; i<m; i++) printf("%d\n",ans[i]); } }