\u5929\u5929\u5728\u5f2f\u9500\u6cb9\u897f\u3002\u3002\u3002\u9893\u5e9f\u4e07\u5206\u3002\u3002\u665a\u4e0a\u603b\u7b97\u53bb\u6c34\u4e86\u9053\u9898\u3002\u3002\u6211\u65e0\u804a\u4e2d\u60f3\u51fa\u4e00\u4e2a\u5f88SB\u7684Lca\u3002\u3002\u3002
\u5c31\u662f\u628a\u8fd9\u9897\u6811\u6811\u94fe\u5256\u5206\uff08\u4e0d\u7528\u7ebf\u6bb5\u6811\u7684\uff0c\u53ea\u9700\u8981\u8bb0\u5f55\u6bcf\u4e2a\u70b9\u5bf9\u5e94\u5f53\u8def\u5f84\u7684\u6700\u9ad8\u70b9\uff09\u3002\u3002\u3002
\u7136\u540e\u8003\u8651u\u548cv\u7684Lca\uff08\u5047\u8bbeu\u7684\u6df1\u5ea6\u5927\u4e8ev\uff09\u3002\u3002\u5982\u679c\u5728\u540c\u4e00\u6761\u94fe\u4e2d\u5c31\u662fv\u3002\u3002
\u5426\u5219\u7684\u8bdd\u8bbeu\u7684\u8def\u5f84\u6700\u9ad8\u70b9\u8981\u6df1\u4e8ev\u7684\u8def\u5f84\u6700\u9ad8\u70b9\uff0c\u90a3\u4e48\u663e\u7136Lca\u4e0d\u53ef\u80fd\u5728u\u7684\u8def\u5f84\u4e2d\uff0c\u5c06u\u6362\u6210u\u7684\u8def\u5f84\u6700\u9ad8\u70b9\u7684\u7236\u8282\u70b9\u3002\u3002\u3002\u7136\u540e\u5c31\u8fd9\u9012\u5f52\u4e0b\u53bb\u3002\u3002\u3002
\u989d\u3002\u3002\u65f6\u95f4\u590d\u6742\u5ea6LogN\u3002\u3002\u9884\u5904\u7406\u590d\u6742\u5ea6\u662fO(N)\u7684\u3002\u3002\u5e38\u6570\u53c8\u6bd4\u7ebf\u6bb5\u6811\u90a3\u4e2a\u8981\u5c0f\u3002\u3002\u901f\u5ea6\u6bd4\u8bb0\u5f552^k\u7956\u5148\u90a3\u4e2a\u548c\u7ebf\u6bb5\u6811\u90fd\u8981\u5feb\u4e00\u4e9b\u3002\u3002\u6811\u94fe\u5256\u5206\u8fd8\u53ef\u4ee5\u5199Bfs..\u62d2\u7edd\u7206stack\u3002\u3002\u8fd8\u662f\u633a\u4e0d\u9519\u6ef4(*^__^*) \u563b\u563b\u3002\u3002\u3002
Code\uff1a\uff08\u9898\u76ee\u662fUral\u4e0a\u7684Tree\uff09
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define tr(e,x) for(eit e=x.begin();e!=x.end();e++)
#define printTime cout<<"Time:"<<pre-clock()<<endl;pre=clock();
const int inf=~0U>>1,maxn=50000;
using namespace std;
int n,q;
struct Edge
{
int t,c;
Edge(int _t,int _c):t(_t),c(_c){}
};
vector<Edge> E[maxn];
typedef vector<Edge>::iterator eit;
void AddEdge(int s,int t,int c)
{
E[s].pb(Edge(t,c));
E[t].pb(Edge(s,c));
}
void Init()
{
scanf("%d",&n);int s,t,c;
rep(i,n-1)
{
scanf("%d%d%d",&s,&t,&c);
AddEdge(s,t,c);
}
}
int D[maxn],C[maxn],F[maxn],Size[maxn];
int Q[maxn],h,t,Own[maxn];
void BFS(int vs)
{
h=t=0;
for(Q[t++]=vs,F[vs]=-1,D[vs]=0,C[vs]=0;h<t;h++)
{
int x=Q[h];
tr(e,E[x])if(e->t!=F[x])
{
F[e->t]=x;C[e->t]=C[x]+e->c;
D[e->t]=D[x]+1;Q[t++]=e->t;
}
}
for(int i=h-1;i>=0;i–)
{
int x=Q[i];Size[x]=1;
tr(e,E[x])if(e->t!=F[x])Size[x]+=Size[e->t];
}
memset(Own,-1,sizeof Own);
for(int i=0;i<h;i++)
{
int a=Q[i];
int x=a,next;if(Own[x]>=0)continue;
for(;;x=next)
{
next=-1;Own[x]=a;
tr(e,E[x])if(e->t!=F[x])
if(next==-1||Size[e->t]>Size[next])
next=e->t;
if(next==-1)break;
}
}
}
int Lca(int u,int v)
{
for(;;)
{
if(D[u]<D[v])swap(u,v);
if(Own[u]==Own[v])return v;
if(D[Own[u]]<D[Own[v]])swap(u,v);
u=F[Own[u]];
}
}
int Query(int u,int v)
{
int lca=Lca(u,v);
return C[u]+C[v]-2*C[lca];
}
void Solve()
{
scanf("%d",&q);int u,v;
rep(i,q)
{
scanf("%d%d",&u,&v);
printf("%dn",Query(u,v));
}
}
int main()
{
\/\/freopen("in","r",stdin);
Init();
BFS(0);
Solve();
} <\/p>\n","protected":false},"excerpt":{"rendered":"
\u5929\u5929\u5728\u5f2f\u9500\u6cb9\u897f\u3002\u3002\u3002\u9893\u5e9f\u4e07\u5206\u3002\u3002\u665a\u4e0a\u603b\u7b97\u53bb\u6c34\u4e86\u9053\u9898\u3002\u3002\u6211\u65e0\u804a\u4e2d\u60f3\u51fa\u4e00\u4e2a\u5f88SB\u7684Lca\u3002\u3002\u3002\u5c31\u662f\u628a\u8fd9\u9897\u6811\u6811\u94fe\u5256\u5206\uff08\u4e0d\u7528\u7ebf\u6bb5\u6811\u7684\uff0c\u53ea\u9700\u8981\u8bb0\u5f55\u6bcf\u4e2a\u70b9\u5bf9\u5e94\u5f53\u8def\u5f84\u7684\u6700\u9ad8\u70b9\uff09\u3002\u3002\u3002\u7136\u540e\u8003\u8651u\u548cv\u7684Lca\uff08\u5047\u8bbeu\u7684\u6df1\u5ea6\u5927\u4e8ev\uff09\u3002\u3002\u5982\u679c\u5728\u540c\u4e00\u6761\u94fe\u4e2d\u5c31\u662fv\u3002\u3002\u5426\u5219\u7684\u8bdd\u8bbeu\u7684\u8def\u5f84\u6700\u9ad8\u70b9\u8981\u6df1\u4e8ev\u7684\u8def\u5f84\u6700\u9ad8\u70b9\uff0c\u90a3\u4e48\u663e\u7136Lca\u4e0d\u53ef\u80fd\u5728u\u7684\u8def\u5f84\u4e2d\uff0c\u5c06u\u6362\u6210u\u7684\u8def\u5f84\u6700\u9ad8\u70b9\u7684\u7236\u8282\u70b9\u3002\u3002\u3002\u7136\u540e\u5c31\u8fd9\u9012\u5f52\u4e0b\u53bb\u3002\u3002\u3002\u989d\u3002\u3002\u65f6\u95f4\u590d\u6742\u5ea6LogN\u3002\u3002\u9884\u5904\u7406\u590d\u6742\u5ea6\u662fO(N)\u7684\u3002\u3002\u5e38\u6570\u53c8\u6bd4\u7ebf\u6bb5\u6811\u90a3\u4e2a\u8981\u5c0f\u3002\u3002\u901f\u5ea6\u6bd4\u8bb0\u5f552^k\u7956\u5148\u90a3\u4e2a\u548c\u7ebf\u6bb5\u6811\u90fd\u8981\u5feb\u4e00\u4e9b\u3002\u3002\u6811\u94fe\u5256\u5206\u8fd8\u53ef\u4ee5\u5199Bfs..\u62d2\u7edd\u7206stack\u3002\u3002\u8fd8\u662f\u633a\u4e0d\u9519\u6ef4(*^__^*) \u563b\u563b\u3002\u3002\u3002Code\uff1a\uff08\u9898\u76ee\u662fUral\u4e0a\u7684Tree\uff09#include <vector>#include <algorithm>#include <utility>#include <iostream>#include <cstdio>#include <cmath>#include <cstdlib>#include <set>#include <map>#include <cstring>#include <time.h>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_back#define Debug(x) cout<<#x<<"="<<x<<endl;#define For(i,l,r) for(int i=l;i<=r;i++)#define tr(e,x) for(eit e=x.begin();e!=x.end();e++)#define printTime cout<<"Time:"<<pre-clock()<<endl;pre=clock();const int inf=~0U>>1,maxn=50000;using namespace std;int n,q;struct Edge{ int t,c; Edge(int _t,int _c):t(_t),c(_c){}};vector<Edge> E[maxn];typedef vector<Edge>::iterator eit;void AddEdge(int s,int t,int c){ E[s].pb(Edge(t,c)); E[t].pb(Edge(s,c));}void Init(){ scanf("%d",&n);int s,t,c; rep(i,n-1) { scanf("%d%d%d",&s,&t,&c); […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/321"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=321"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/321\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=321"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=321"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=321"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}