HDU 4836 The Query on the Tree lca || 欧拉序列 || 动态树-白红宇

HDU 4836 The Query on the Tree lca || 欧拉序列 || 动态树

阅读量：7109 次

发布时间：2019-06-28

本文共 1444 字，大约阅读时间需要 4 分钟。

lca的做法还是非常明显的。简单粗暴。

只是不是正解，假设树是长链就会跪。直接变成O(n)、、

最后跑的也挺快，出题人还是挺阳光的。。

动态树的解法也是听别人说能ac的，预计就是放在splay上剖分一下，做法还是比較复杂的。，，

来一发lca：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  using namespace std;#define INF 0x3f3f3f3f#define eps 1e-8#define pi acos(-1.0)typedef long long ll;const int maxn=20010;int head[maxn],tol,dp[maxn],fa[maxn][20],dep[maxn],weight[maxn];struct Edge{ int next,to; Edge(int _next=0,int _to=0){ next=_next;to=_to; }}edge[10*maxn];void addedge(int u,int v){ edge[tol]=Edge(head[u],v); head[u]=tol++;}void bfs(int s){ queue
                   
                     q; dep[s]=0,fa[s][0]=s; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=1;i<20;i++)fa[u][i]=fa[fa[u][i-1]][i-1]; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==fa[u][0])continue; fa[v][0]=u; dep[v]=dep[u]+1; q.push(v); } }}int LCA(int x,int y){ if(dep[x]
                    
                     =0;i--)if((1<
                     
                      =0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; return fa[x][0];}void dfs(int u,int pre){ dp[u]=weight[u]; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==pre)continue; dfs(v,u); dp[u]+=dp[v]; }}int move(int x,int d){ for(int i=19;i>=0;i--) if(d&(1<
                      
                       >T; for(int t=1;t<=T;t++){ int n; scanf("%d",&n); memset(head,-1,sizeof(head));tol=0; for(int i=1;i