http://www.lydsy.com/JudgeOnline/problem.php?id=3732

/*
Kruskal 最小生成树
树链剖分 最大值查询
注意：可能会有几块不联通的图
*/

#include
#include
#include
#include
#include

using namespace std;
const int N = ;

#define gc getchar()
#define lson jd << 1
#define rson jd << 1 | 1

int n, m, k, now = , tim, ans;
int bef[N], data[N], fat[N], head[N], tree[N], topp[N], fa[N], son[N], siz[N], deep[N];
struct Node_1{int u, v, w;} E[N << ];
struct Node_2{int u, v, w, nxt;} G[N << ];
struct Node_3{int l, r, Max;} T[N << ];

bool cmp(Node_1 a, Node_1 b) {return a.w < b.w;}

struct Bzoj_3732{

inline int read(){  
    int x = ; char c = gc;  
    while(c < '' || c > '') c = gc;  
    while(c >= '' && c <= '') x = x \*  + c - '', c = gc;  
    return x;  
}

inline int getf(int x) {return fat\[x\] == x ? x : fat\[x\] = getf(fat\[x\]);}  
inline void add(int u, int v, int w) {G\[now\].v = v; G\[now\].w = w; G\[now\].nxt = head\[u\]; head\[u\] = now ++;}

inline void Kruskal(){  
    int js();  
    for(int i = ; i <= m; i ++){  
        int u = E\[i\].u, v = E\[i\].v;  
        int fu = getf(u), fv = getf(v);  
        if(fu != fv) {  
            js ++; fat\[fu\] = fv;  
            add(u, v, E\[i\].w);  
            add(v, u, E\[i\].w);  
        }  
        if(js == n - ) return ;  
    }  
}

void dfs\_find\_son(int u, int f\_, int dep){  
    fa\[u\] = f\_;  
    deep\[u\] = dep;  
    siz\[u\] = ;  
    for(int i = head\[u\]; ~ i; i = G\[i\].nxt){  
        int v = G\[i\].v;  
        if(v != f\_){  
            data\[v\] = G\[i\].w;  
            dfs\_find\_son(v, u, dep + );  
            siz\[u\] += siz\[v\];  
            if(siz\[v\] > siz\[son\[u\]\]) son\[u\] = v;  
        }  
    }  
}

void dfs\_to\_un(int u, int tp){  
    topp\[u\] = tp;  
    tree\[u\] = ++ tim;  
    bef\[tim\] = u;  
    if(!son\[u\]) return ;  
    dfs\_to\_un(son\[u\], tp);  
    for(int i = head\[u\]; ~ i; i = G\[i\].nxt){  
        int v = G\[i\].v;  
        if(v != fa\[u\] && v != son\[u\]) dfs\_to\_un(v, v);  
    }  
}

void build\_tree(int l, int r, int jd){  
    T\[jd\].l = l; T\[jd\].r = r;  
    if(l == r) {T\[jd\].Max = data\[bef\[l\]\]; return ;}  
    int mid = (l + r) >> ;  
    build\_tree(l, mid, lson);  
    build\_tree(mid + , r, rson);  
    T\[jd\].Max = max(T\[lson\].Max, T\[rson\].Max);  
}

void Sec\_A(int l, int r, int jd, int x, int y){  
    if(x <= l && r <= y) {ans = max(ans, T\[jd\].Max); return ;}  
    int mid = (l + r) >> ;  
    if(x <= mid) Sec\_A(l, mid, lson, x, y);  
    if(y > mid)  Sec\_A(mid + , r, rson, x, y);  
}

inline int Sec\_A\_imp(int x, int y){  
    int tp1 = topp\[x\], tp2 = topp\[y\], ret = ;  
    while(tp1 != tp2){  
        if(deep\[tp1\] < deep\[tp2\]) swap(x, y), swap(tp1, tp2);  
        ans = ;  
        Sec\_A(, n, , tree\[tp1\], tree\[x\]);  
        ret = max(ans, ret);  
        x = fa\[tp1\];  
        tp1 = topp\[x\];  
    }  
    if(x == y) return ret;  
    if(deep\[x\] < deep\[y\]) swap(x, y);  
    ans = ;  
    Sec\_A(, n, , tree\[y\] + , tree\[x\]);  
    ret = max(ret, ans);  
    return ret;  
}  

}AC;

int main()
{
n = AC.read(), m = AC.read(); k = AC.read();
for(int i = ; i <= n; i ++) fat[i] = i, head[i] = -;
for(int i = ; i <= m; i ++)
E[i].u = AC.read(), E[i].v = AC.read(), E[i].w = AC.read();
sort(E + , E + m + , cmp);
AC.Kruskal();
for(int i = ; i <= n; i ++) if(!deep[i]) AC.dfs_find_son(i, , );
for(int i = ; i <= n; i ++) if(!topp[i]) AC.dfs_to_un(i, i);
AC.build_tree(, n, );
while(k --){
int x = AC.read(), y = AC.read();
int Answer = AC.Sec_A_imp(x, y);
printf("%d\n", Answer);
}

return ;  

}

与noip2013货车运输相似（一模一样）

货车运输：最大生成树 + 最小值查询

此题       ：最小生成树 + 最大值查询

货车运输改几行代码就A了

#include
#include
#include
#include
#include
#include

using namespace std;
const int N = ;

#define oo 99999999

struct Node{
int u, v, w;
}S[N << ];
struct Edge{
int u, v, w, nxt;
}E[N << ];

int now = , n, m, js;
int head[N], p[N], f[N][], g[N][], deep[N];

inline int read(){
int x = ; char c = getchar();
while(c < '' || c > '') c = getchar();
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x;
}

inline bool cmp(Node a, Node b){
return a.w < b.w;
}

int getf(int x){
return p[x] == x ? x : p[x] = getf(p[x]);
}

void add(int u, int v, int w){
E[now].v = v;
E[now].w = w;
E[now].nxt = head[u];
head[u] = now ++;
}

inline void Kruskal(){
for(int i = , doen = ; i <= (m << ) && doen < n; i ++){
int u = S[i].u, v = S[i].v;
int pu = getf(u), pv = getf(v);
if(pu != pv){
p[pu] = pv;
add(u, v, S[i].w);
add(v, u, S[i].w);
doen ++;
}
}
}

void make_deep(int u, int depth){
deep[u] = depth;
for(int i = head[u]; ~ i; i = E[i].nxt){
int v = E[i].v;
if(!deep[v]){
f[v][] = u;
g[v][] = E[i].w;
make_deep(v, depth + );
}
}
}

inline void make_jump(){
for(int j = ; ( << j) <= n; j ++)
for(int i = ; i <= n; i ++)
if(f[i][j - ]) f[i][j] = f[f[i][j - ]][j - ], g[i][j] = max(g[i][j - ], g[f[i][j - ]][j - ]);
}

inline int lca(int x, int y){
int ret = -;
if(x == y) return ;
if(deep[x] < deep[y]) swap(x, y); int k = log2(deep[x]); for(int i = k; i >= ; i --){
if(deep[f[x][i]] >= deep[y]){
ret = max(ret, g[x][i]);
x = f[x][i];
}
}
if(x == y) return ret;
for(int i = k; i >= ; i --){
if(f[x][i] != f[y][i]){
ret = max(ret, max(g[x][i], g[y][i]));
x = f[x][i];
y = f[y][i];
}
}
ret = max(ret, max(g[x][], g[y][]));
return ret;
}

int main()
{
n = read();
m = read();
int T = read();
for(int i = ; i <= n; i ++) head[i] = -, p[i] = i;
for(int i = ; i <= m; i ++) S[i].u = read(), S[i].v = read(), S[i].w = read();
sort(S + , S + m + , cmp);
Kruskal();
for(int i = ; i <= n; i ++) if(!deep[i]) make_deep(i, );//可能会有多块
make_jump();
while(T --){
int x = read(), y = read();
int answer = lca(x, y);
printf("%d\n", answer);
}
return ;
}