lca分析,semi前缀

# include bits/stdc.husingnamespacestd； const int N=1e6 10； 结构边缘{ int to，nxt，val； }d[N]； int head[N]，cnt=1； voidadd(intu，int v，int k ) d[CNT]=) edge ) v，head[u]，k}，head[u]=cnt； }int n，m，son[N]，siz[N]，deep[N]，fa[N][20]，an[N]； int top[N]； voidDFS(intu，int father，int depth ) {siz[u]=1，deep[u]=depth，fa[u][0]=father； int maxson=-1； for(intI=head[u]； I； I=d[I].nxt(intv=d[I].to； if(v==Father ) continue； DFS(v，u，depth 1)； siz[u]=siz[v]； if(maxsonsiz[v] ) maxson=siz[v]，son[u]=v； }voidDFS2(intx，int t ) { top[x]=t； if(son[x]==0)返回； DFS2(son[x]，t )； for(intI=head[x]； I； I=d[I].nxt(intv=d[I].to； if(v！=son[x]v！=fa[x][0](DFS2) v，v )； }intquery(inta，int b ) ) while ) top[a]！=top[b](if ) deep[top[a] ) deep[top[b] ) a=fa[top[a] )0)； }else{ b=fa[top[b]][0]； } }返回deep [ a ] deep [ b ]？ b:a； }int dis[N]； voidDFS3(intx，int fa ) for ) intI=head[x]； I； I=d[I].nxt(intv=d[I].to，val=d[i].val； if(v==fa ) continue； dis[v]=dis[x] val； //coutvalendl； DFS3(v，x )； }}int main () Scanf ) ' %d%d '，n，m )； for(intI=1； in； I ) { int a，b，k； 扫描(% d % d % d )、a、b、k )； add(a，b，k )； add(b，a，k )； } DFS (1，0，1 )； DFS2(1，1 )； DFS3(1，0 )； //coutdis[2]endl； //int q； Scanf('%d '，q )； wile(m---- ) { int a，b； 扫描(' % d % d )、a、b )； intLCapos=query(a，b )； printf(%d(n )，dis[a] dis[b]-2*dis[lcapos] )； }