显然可以用LCT维护kruskal重构树。或者启发式合并维护kruskal重构树的倍增数组虽然多了个log也不一定比LCT慢吧。

　　当然这里的kruskal重构树几乎只是把树上的边权换成了点权，并不重要。

　　我们要查询的是树上两点间路径边权最大值。显然要并查集按秩合并一波。然后……并查集的树高就是log啊？维护个鬼的倍增数组啊直接暴力啊？

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define N 500010char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,m,lastans,fa[N],len[N],deep[N];bool flag[N];int find(int x){ return fa[x]==x?x:find(fa[x]);}void merge(int x,int y,int i){ int p=find(x),q=find(y); if (p!=q) { if (deep[p]