HDU 2586 How far away LCA倍增模闆

題目很簡單，沒有考什麼思維；今天AC的時候發現以前我學lca的時候就在搞這題，而且已經WA，TLE，MLE，RE等等各種14發，，，

思路：額，，這尼瑪還要寫思路？？？？

模闆：看代碼

在dfs的時候maxh忘了更新了，居然TLE，，，添上就A了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
using namespace std ;

const int N = 40000 + 11 ;

struct Greaph {
	struct Edge {
		int e ;
		int w ;
		int next ;
	} ;

	Edge err[N<<1] ;
	int head[N] ;
	int idx ;
	int anc[N][30] ;
	int cost[N] ;
	int depth[N] ;
	int n , m ;
	int maxh ;

	void add_edge(int a , int b , int w) {
	    err[idx].e = b ;
	    err[idx].w = w ;
	    err[idx].next = head[a] ;
	    head[a] = idx ++ ;
    }

	void addinfo() {
		memset(head , -1 , sizeof(head));
		idx = 1 ;
		int a , b  , w ;
		for(int i = 1 ; i < n ;++i) {
			scanf("%d%d%d" ,&a ,&b ,&w) ;//無向邊，，開始的時候居然忘了
			add_edge(a , b , w) ;
			add_edge(b , a , w) ;
		}
	}

	void dfs(int site , int fa) {
		for(int i = head[site] ; i != -1 ; i = err[i].next) {
			int e = err[i].e ;
			if(e != fa) {
				depth[e] = depth[site] + 1 ;
				cost[e] = cost[site] + err[i].w ;
				anc[e][0] = site ;
				dfs(e , site) ;
			}
		}
		if(depth[site] > maxh) maxh = depth[site];
	}

	void swim(int& a , int h) {
	    int k = 0 ;
	    while(h) {
            if(h&1) a = anc[a][k] ;
            ++k ;
            h >>= 1;
	    }
	}

	int find(int a, int b) {
		if(depth[a] < depth[b]) {int t = a ;a =b ;b = t;}
		swim(a , depth[a] - depth[b]) ;
		if(a == b) return a;
		while(true) {
            int i ;
			for(i= 0 ; anc[a][i] != anc[b][i] ; ++i)  ;
			if(i == 0) return anc[a][0] ;//是anc[a][0] , 不是a，，，
			a = anc[a][i-1] ;
			b = anc[b][i-1] ;
		}
		return -1 ;
	}

	void std_fun() {
		addinfo() ;
		depth[1] = 1 ;	cost[1] = 0 ; maxh = 0 ; anc[1][0] = 1 ;
		dfs(1 , 0);
		for(int i = 1 ; (1<<i) <= maxh ; ++i) {//這裡是先後順序不能搞錯了，，，，，千萬，，，，
			for(int j = 1 ; j <= n ; ++j) {
				anc[j][i] = anc[anc[j][i-1]][i-1] ;
			}
		}
		int a, b ;
		while(m--) {
			scanf("%d%d",&a ,&b) ;
			int ancestor = find(a , b) ;
			assert(ancestor != -1) ;
			printf("%d\n" , cost[a] + cost[b] - cost[ancestor]- cost[ancestor]) ;
		}
	}
}g ;

int main() {
    int t ;
    scanf("%d",&t);
	while(t--) {
        scanf("%d%d",&g.n ,&g.m);
		g.std_fun() ;
	}
}