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

题意：

前言：

时间给的有点多，8秒，其实正解1秒足够，8秒导致很多人只用了树链剖分O(1)修改  暴力查询都能过。

更好的解法是树上树套树（学习别人代码的）

时间复杂度O(Nlog^3N)

自己想到的做法是树上动态主席树，发现有点难实现（树状数组维护dfs序，线段树维护权值 ）发现不好做，

因为树上的节点并不是连续的，树状数组更新的时候dfs序又是连续的，可能会导致左儿子的点更新到右儿子的线段树上面去了。

 

看了别人的代码没想到还可以反过来（树状数组维护权值，线段树维护dfs序）

 

思想：树剖解决，我们只维护每个节点和重儿子的边权，

那么当一个节点权值改变时，也只需要修改该节点和其重儿子的边权，

若该节点是其父亲节点的重儿子，则多修改一条该节点和其父亲节点的边权。

查询操作时，若该节点不是父亲节点的重儿子，则暴力计算一次该节点和父亲节点的边权。

改为：查询操作时对所有小于k的树状树节点查询dfs序为fa到u  fa到v 的数量

树链剖分+树状数组+动态开点线段树 

时间复杂度O(Nlog^3N)

1、树链剖分方便维护dfs的维护

2、树状数组是对每一条边的权值进行维护 （gcd为k）

3、动态开点线段树真正的在维护每一个以k为根节点的线段树  的dfs序个数

4、假设查询小于k的，呢么从树状数组那进行前缀查询 树状数组又传递树链剖分得到的dfs序区间

代码就没有自己打了，拿的别人的，有点长

/*树剖解决，我们只维护每个节点和重儿子的边权，那么当一个节点权值改变时，也只需要修改该节点和其重儿子的边权，若该节点是其父亲节点的重儿子，则多修改一条该节点和其父亲节点的边权。查询操作时，若该节点不是父亲节点的重儿子，则暴力计算一次该节点和父亲节点的边权。改为：查询操作时对所有小于k的树状树节点查询dfs序为fa到u  fa到v 的数量树链剖分+树状数组+动态开点线段树 时间复杂度O(Nlog^3N)树链剖分方便维护dfs的维护树状数组是对每一条边的权值进行维护 gcd为k动态开点线段树真正的在维护每一个以k为根节点的线段树  的dfs序个数假设查询小于k的，呢么从树状数组那进行前缀查询 树状数组又传递树链剖分得到的dfs序区间*/#include
   
    #define PB push_backusing namespace std;const int N=1e6+10,M=2e7+10,mod=998244353;int n,q;int a[N];int w[N];int cnt;int son[N],siz[N],fa[N],de[N];int dfn[N],top[N];vector
    
     G[N];/*树链剖分部分预处理*/void dfs(int x){    siz[x]=1;    son[x]=-1;    for(int i=0;i
     
      siz[son[x]])son[x]=y;        }    }}void dfs2(int x,int t){    dfn[x]=++cnt;    top[x]=t;    if(siz[x]==1)return;    dfs2(son[x],t);    for(int i=0;i
      
       de[y])return y;    else return x;}/*动态开点权值线段树部分*/int rt[N],tot;int s[M],ls[M],rs[M];void update(int loc,int &x,int p,int l,int r){    if(x==0)x=++tot;    if(l==r){        s[x]+=p;        return;    }    int mid=l+r>>1;    if(loc<=mid)update(loc,ls[x],p,l,mid);    else update(loc,rs[x],p,mid+1,r);    s[x]=s[ls[x]]+s[rs[x]];}int query(int a,int b,int x,int l,int r){    if(x==0)return 0;    if(a==l&&b==r)return s[x];    int mid=l+r>>1;    if(b<=mid)return query(a,b,ls[x],l,mid);    else if(a>mid)return query(a,b,rs[x],mid+1,r);    else return query(a,mid,ls[x],l,mid)+query(mid+1,b,rs[x],mid+1,r);}/*树状数组部分*/void upd(int pos,int k,int p){//某个dfs序pos，权值gcd:k  p 1 或-1    for(;k<=1000000;k+=k&-k){        update(pos,rt[k],p,1,n);//k 这个线段树    }}int que2(int l,int r,int k){//dfs序为区间l，r信息    int ans=0;    for(;k;k-=k&-k){        ans+=query(l,r,rt[k],1,n);    }    return ans;}int que1(int u,int anc,int k){    int ans=0;    while(top[u]!=top[anc]){        ans+=que2(dfn[top[u]],dfn[u],k);//top[u]到u的                ans+=(__gcd(a[top[u]],a[fa[top[u]]])<=k);//*(top[u]==son[fa[top[u]]]);               u=fa[top[u]];    }    //cout<<"FUCK2 "<
       
        <<' '<
        <<' '<
         
          <
         
       
      
     
    
   

转载地址：https://ccsudeer.blog.csdn.net/article/details/106280797 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！