[codevs 2370] 작은 기관실 의 나무

입력 설명 Input Description

     n，   n-1         u，v, c 。     u      v      c    。
 n+1      m   m   。   m          u ，v            

출력 설명 Output Description
모두 m 줄 이 있 고 각 줄 의 정 수 는 이번 문의 에서 얻 은 가장 짧 은 거 리 를 나타 낸다.
 알고리즘: LCA 배가.
대체적인 사고방식: 변경 을 건설 할 때 쌍방 향 으로 건설 하 는데 주의해 야 할 것 은 뿌리 결점 은 스스로 선택해 야 한 다 는 것 이다. 여기 서 선택 한 것 은 0 이다.grand [i] [j] 로 i 결점 2 ^ j 가 있 는 조상 을 표시 하고 dis [i] [j] 로 조상 과 의 거 리 를 표시 합 니 다.그리고 점프 할 때 dis 의 방식 을 바 꾸 는 것 에 주의 하 세 요.
몇 가지 알림: LCA 는 1. 양 방향 변 을 기억 하고 구조 체 를 열 때 max x 는 왼쪽 으로 한 명 밀어 야 합 니 다.2. 20 에서 0 은 i -, + 가 아 닙 니 다.3. grand 배열 은 20 을 재생 하려 면 배열 이 적어도 2 차원 에서 21 을 열 고 22 까지 하 는 것 이 좋 습 니 다.4. 반드시 dfs root 결점 을 먼저 해 야 합 니 다.↑ 모두 언어 를 제대로 배우 지 못 한 솥 이다 = =
코드:

#include 
#include 

using namespace std;

const int maxx = 50000 + 100;

int head[maxx],depth[maxx];
int grand[maxx][20+2],dis[maxx][20+2];
bool done[maxx];
int n,m,x,y,z,num,root;

struct Edge{
    int next;
    int to;
    int value;
}Edges[maxx<<1];

inline int Read(){
    int x=0,f=1;char c=getchar();
    while(c>'9'||c='0'&&c<='9') {x=x*10+c-'0'; c=getchar();}
    return x*f;
}

void Add(int x,int y,int z){
    Edges[++num].to=y;
    Edges[num].next=head[x];
    Edges[num].value=z;
    head[x]=num;
}

void Dfs(int x){
    done[x]=true;
    for(int i=1;i<=20;i++){
		if((1< depth[x]) break;
		grand[x][i]=grand[grand[x][i-1]][i-1];
		dis[x][i]=dis[x][i-1]+dis[grand[x][i-1]][i-1];
    }
    for(int i=head[x];i;i=Edges[i].next){
		int now=Edges[i].to;
		if(done[now]) continue;
		depth[now]=depth[x]+1;
		grand[now][0]=x;
		dis[now][0]=Edges[i].value;
		Dfs(now);
    }
}

inline int Lca(int x,int y){
    int Ans=0;
    if(depth[x]>depth[y]) swap(x,y);
    int d=depth[y]-depth[x];
    for(int i=0;i<=20;i++){
		if((1<=0;i--){
		if(grand[x][i]!=grand[y][i]){
	    	Ans += dis[x][i];
	    	Ans += dis[y][i];
	    	x=grand[x][i];
	    	y=grand[y][i];
		}
    }
    if(x==y) return Ans;
    else{
		Ans+=dis[x][0]+dis[y][0];
		return Ans;
    }
}

int main(){
    n=Read();
    for(int i=1;i