CS杯2021 E

最近霉运连连，微信消息no response搞得去蹭曾老师的球台vp，QQ因为某事炸号

---

E题主要是先树链剖分，然后像吉司机线段树那样对一些有规律的区间进行标记，减少操作数。

莫比乌斯函数打表发现最多加一次就可以到达的循环中或者直接对应的莫比乌斯函数值为0即：

code：

#include <bits/stdc++.h>

using namespace std;

using ll=long long;

ll n,q, a[(int)1e6+9],M,p[(int)4e6+9],dep[(int)1e5+9],sz[(int)1e5+9],top[(int)1e5+9],son[(int)1e5+9],f[(int)1e5+9],id[(int)1e5+9],cov[(int)1e5+9];
bitset<(int)5e6+900> vis;
int mu[(int)5e6+900],pr[(int)5e6+900],cnt,tot;

const int maxn=1e5+9;
struct Node{
    int l,r,tag,cs;
    ll v;
}tr[maxn<<2];
bitset<(maxn*4ll)> upd;

void build(int l,int r,int tot){
    if(l==r){
        tr[tot].v=a[cov[l]];
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,tot<<1),build(mid+1,r,(tot<<1)|1);
    tr[tot].v=tr[tot<<1].v+tr[(tot<<1)|1].v;
}

void update(int nl,int nr,int tot,int l,int r){
    int mid=(nl+nr)>>1;
    if(tr[tot].cs&&nl!=nr){
        tr[tot<<1].v+=tr[tot<<1].tag*(tr[tot].cs&1?1ll:0ll),tr[tot<<1|1].v+=tr[tot<<1|1].tag*(tr[tot].cs&1?1ll:0ll);
        tr[tot<<1].cs+=tr[tot].cs,tr[(tot<<1)|1].cs+=tr[tot].cs;
        tr[tot<<1].tag*=(tr[tot].cs&1?-1ll:1ll),tr[tot<<1|1].tag*=(tr[tot].cs&1?-1ll:1ll);
        tr[tot].cs=0;
    }
    if(upd[tot]&&l<=nl&&nr<=r){
        tr[tot].cs+=1;
        tr[tot].v+=tr[tot].tag,tr[tot].tag*=-1ll;
        return ;
    }
    if(nl==nr){
        tr[tot].v+=mu[tr[tot].v];
        if(mu[tr[tot].v]==0){
            upd[tot]=1,tr[tot].tag=0;
            return;
        }
        ll nxt=tr[tot].v+mu[tr[tot].v],nnxt=nxt+mu[nxt];
        if(nnxt==tr[tot].v){
            upd[tot]=1;
            tr[tot].tag=mu[tr[tot].v];
        }
        return ;
    }
    if(mid>=l)update(nl,mid,tot<<1,l,r);
    if(mid<r)update(mid+1,nr,(tot<<1)|1,l,r);
    tr[tot].v=tr[tot<<1].v+tr[(tot<<1)|1].v;
    if(upd[tot<<1]&&upd[tot<<1|1]){
        upd[tot]=1;
        tr[tot].tag=tr[tot<<1].tag+tr[tot<<1|1].tag;
    }
}

ll Sum(int nl,int nr,int tot,int l,int r){
    ll mid=(nl+nr)>>1,res=0;
    if(tr[tot].cs&&nl!=nr){
        tr[tot<<1].v+=tr[tot<<1].tag*(tr[tot].cs&1?1ll:0ll),tr[tot<<1|1].v+=tr[tot<<1|1].tag*(tr[tot].cs&1?1ll:0ll);
        tr[tot<<1].cs+=tr[tot].cs,tr[(tot<<1)|1].cs+=tr[tot].cs;
        tr[tot<<1].tag*=(tr[tot].cs&1?-1ll:1ll),tr[tot<<1|1].tag*=(tr[tot].cs&1?-1ll:1ll);
        tr[tot].cs=0;
    }
    if(l<=nl&&nr<=r)return tr[tot].v;
    if(mid>=l)res+=Sum(nl,mid,tot<<1,l,r);
    if(mid<r)res+=Sum(mid+1,nr,(tot<<1)|1,l,r);
    return res;
}

void get_mu()
{
    
    mu[1]=1;
    vis[1]=true;
    for(int i=2;i<=5e6+10;i++)
    {
        if(!vis[i])
        {
            pr[++tot]=i;
            vis[i]=true;
            mu[i]=-1;
        }
        for(int j=1;j<=tot&&i*pr[j]<=5e6+10;j++)
        {
            vis[i*pr[j]]=true;
            if(i%pr[j]==0)
            {
                mu[i*pr[j]]=0;
                break;
            }
            else
            {
                mu[i*pr[j]]=-mu[i];
            }
        }
    }
    return ;
} 

vector<int> g[(int)1e5+9];

void dfs1(int u,int fa,int deep){
    dep[u]=deep,f[u]=fa,sz[u]=1;
    int ma=0;
    for(auto it:g[u]){
        if(it!=fa){
            dfs1(it,u,deep+1);
            sz[u]+=sz[it];
            if(ma<sz[it]){
                ma=sz[it],son[u]=it;
            }
        }
    }
}

void dfs2(int u,int fa){
    top[u]=fa,id[u]=++cnt,cov[id[u]]=u;
    if(!son[u])return ;
    dfs2(son[u],fa);
    for(auto it:g[u]){
        if(it!=son[u]&&it!=f[u]){
            dfs2(it,it);
        }
    }

}

void add(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        update(1,n,1,id[top[u]],id[u]);
        u=f[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    update(1,n,1,id[u],id[v]);
}

ll query(int u,int v){
    ll res=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        res+=Sum(1,n,1,id[top[u]],id[u]);
        u=f[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    res+=Sum(1,n,1,id[u],id[v]);
    return res;
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    get_mu();
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=2,x,y;i<=n;++i){
        cin>>x>>y;
        g[x].push_back(y),g[y].push_back(x);
    }
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,n,1);
    cin>>q;
    for(int i=1,x,y,z;i<=q;++i){
        cin>>x>>y>>z;
        if(x&1){
            add(y,z);
        }else cout<<query(y,z)<<"\n";
    }
    return 0;
}