解题关键：LCA模板题

复杂度：$O(n\log n)$

1 #pragma comment(linker, "/STACK:1024000000,1024000000")  2 #include
     
        3 #include
      
         4 #include
       
          5 #include
        
           6 #include
         
            7 #include
          
            8 typedef long long ll; 9 using namespace std; 10 const int maxn=81000; 11 const int maxm=25; 12 int _pow[maxm],m,n; 13 int head[maxn],tot; 14 int ver[maxn*2],depth[maxn*2],first[maxn],rmq[maxn*2][maxm],id;//5个数组，注意哪个需要乘2 15 ll dis[maxn]; 16 inline int read(){ 17 char k=0;char ls;ls=getchar();for(;ls<'0'||ls>'9';k=ls,ls=getchar()); 18 int x=0;for(;ls>='0'&&ls<='9';ls=getchar())x=(x<<3)+(x<<1)+ls-'0'; 19 if(k=='-')x=0-x;return x; 20 } 21 22 struct edge{ 23 int to,w,nxt; 24 }e[maxn*2];//链式前向星建树 25 26 void init(){ 27 memset(head,-1,sizeof head); 28 tot=0; 29 id=0; 30 } 31 32 void add_edge(int u,int v,int w){ 33 e[tot].to=v; 34 e[tot].w=w; 35 e[tot].nxt=head[u]; 36 head[u]=tot++; 37 } 38 39 void dfs(int u,int fa,int dep){ 40 ver[++id]=u;//第i个访问到的结点编号 41 depth[id]=dep;//第i个访问到的结点深度 42 first[u]=id; 43 for(int i=head[u];i!=-1;i=e[i].nxt){ 44 int v=e[i].to; 45 int w=e[i].w; 46 if(v==fa) continue; 47 dis[v]=dis[u]+w;//dis是先序遍历求 48 dfs(v,u,dep+1); 49 ver[++id]=u;//后序遍历，再次访问父节点 50 depth[id]=dep; 51 } 52 } 53 54 void rmq_init(int n){ 55 int k=int(log(n)/log(2)); 56 for(int i=1;i<=n;++i) rmq[i][0]=i; 57 for(int j=1;j<=k;++j){ 58 for(int i=1;i+_pow[j]-1<=n;++i){ //因为存的是索引 59 int a=rmq[i][j-1],b=rmq[i+_pow[j-1]][j-1]; 60 if(depth[a]
           
            y)swap(x,y); 76 int res=rmq_query(x,y); 77 return ver[res]; 78 } 79 80 int main(){ 81 for(int i=0;i