这题上次用的是线性求LCA过的，数据比较水，当时没有被T掉（不过线性的做法是在线的）。现在重新的分析一下这个问题。在所有的操作都进行完毕以后，这个图形肯定会变成一棵树，而我们的要求是在这棵树上的一条链上求出边权值t的最大值，那么很显然的可以使用树链剖分来解决这个问题（在做这题之前我还不知道LCA也可以获得一条链上的最值）。然后再看这个问题，因为不论是LCA还是树链剖分，都不能够动态的修改树的形状然后维护最值，因此，这样的做法只能够采用离线的做法。最后需要注意的一点是，因为最后求得的这棵树，在时间i的时候已经把后面的操作也加上了，也就是说如果这条链上的最值大于时间i，那么在这个时刻i实际上这两点是没有被联通的。

　　代码如下（LCA）：

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 using namespace std;  6 const int N = 1e5 + 10;  7 const int log_N = 20 + 1;  8 typedef pair
         
           pii;  9  10 int root[N]; 11 int find(int x) {
   return x == root[x] ? x : root[x] = find(root[x]);} 12  13 int n,m,T; 14 int par[log_N][N]; 15 int dep[N]; 16 int op[N],uu[N],vv[N]; 17 vector
          
            G[N]; 18 int mx[log_N][N]; 19 void dfs(int u,int fa,int d) 20 { 21 par[0][u] = fa; 22 dep[u] = d; 23 for(int i=0;i
           
             dep[v]) swap(u, v); 56 for(int k=0;k
            
             > k & 1) 59 { 60 ans = max(ans, mx[k][v]); 61 v = par[k][v]; 62 } 63 } 64 if(u == v) printf("%d\n",ans > i ? -1 : ans); 65 else 66 { 67 for(int k = log_N - 1; k >= 0; k--) 68 { 69 if(par[k][u] != par[k][v]) 70 { 71 ans = max(ans, mx[k][u]); 72 ans = max(ans, mx[k][v]); 73 u = par[k][u]; 74 v = par[k][v]; 75 } 76 } 77 ans = max(ans, max(mx[0][u], mx[0][v])); 78 printf("%d\n",ans > i ? -1 : ans); 79 } 80 } 81 } 82 83 void solve() 84 { 85 init_lca(); 86 for(int i=1;i<=m;i++) 87 { 88 if(op[i] == 2) 89 { 90 solve_lca(uu[i], vv[i], i); 91 } 92 } 93 } 94 95 int main() 96 { 97 scanf("%d",&T); 98 while(T--) 99 {100 scanf("%d%d",&n,&m);101 for(int i=1;i<=n;i++) G[i].clear(), root[i] = i;102 for(int i=1;i<=m;i++)103 {104 scanf("%d%d%d",op+i,uu+i,vv+i);105 if(op[i] == 1)106 {107 int rx = find(uu[i]), ry = find(vv[i]);108 if(rx == ry) continue;109 root[ry] = rx;110 G[uu[i]].push_back(pii(vv[i], i));111 G[vv[i]].push_back(pii(uu[i], i));112 }113 }114 solve();115 }116 return 0;117 }