?pid=2586
给定一棵带权有根树，对于m个查询(u,v)，求得u到v之间的最短距离
那么只要求得LCA(u,v)，dis（u,v)=dis[u]+dis[v]-2*dis[LCA(u,v)]，其中dis[i]表示节点i到根节点root的距离
31MS 4104K 2186 B
maxn=40010;const int maxq=210;;int n,m;struct Edge{int to,w;int next;}edge[maxn<<1];int head[maxn],tot;struct Query{int to,next;int index;}que[maxq<<1];int h[maxn],tt;void addedge(int u,int v,int w){edge[tot].to=v;edge[tot].w=w;edge[tot].next=head[u];head[u]=tot++;}void add_query(int u,int v,int index){que[tt].to=v;que[tt].index=index;que[tt].next=h[u];h[u]=tt++;}int f[maxn],dis[maxn],answer[maxq];bool vis[maxn],in[maxn];int find(int x){return f[x]==-1 ? x:f[x]=find(f[x]);}void Union(int a,int b){int t1=find(a);int t2=find(b);if(t1!=t2) f[t2]=t1;}void LCA(int u){vis[u]=1;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(vis[v]) continue;dis[v]=dis[u]+edge[i].w;LCA(v);Union(u,v);}for(int i=h[u];i!=-1;i=que[i].next){int v=que[i].to;if(vis[v]){answer[que[i].index]=dis[u]+dis[v]-2*dis[find(v)];}}}void Init(){tot=tt=0;memset(h,-1,sizeof(h));memset(head,-1,sizeof(head));memset(f,-1,sizeof(f));memset(vis,false,sizeof(vis));memset(in,false,sizeof(in));memset(dis,0,sizeof(dis));}int main(){T,u,v,w;cin>>T;while(T–){Init();scanf(“%d%d”,&n,&m);for(int i=0;i<n-1;++i){scanf(“%d%d%d”,&u,&v,&w);addedge(u,v,w);addedge(v,u,w);in[v]=true;}for(int i=0;i<m;++i){scanf(“%d%d”,&u,&v);add_query(u,v,i);add_query(v,u,i);}for(int i=1;i<=n;++i){if(in[i]==false){LCA(i);break;}}for(int i=0;i<m;++i){printf(“%d\n”,answer[i]);}}return 0;}
，一起吃早餐，午餐，晚餐。或许吃得不好，
