[GXOI/GZOI2019]旧词

爱被打了一巴掌 2021-11-11 14:50 232阅读 0赞

# 题目描述 #

给定一棵 n 个点的有根树，节点标号1∼n，1号节点为根。  
给定常数 k。  
给定Q个询问，每次询问给定 x,y。  
求：

$\\sum\_\{i \\leq x\}dep\[lca(i,y)\]^\{k\}$

lca(x,y) 表示节点x与节点y在有根树上的最近公共祖先。  
depth(x) 表示节点x的深度，根节点的深度为 1。  
由于答案可能很大，你只需要输出答案模998244353 的结果。

# 题解 #

先考虑k为1，对于每一对点，只要求lca的深度，而不是lca是谁，那么就有一种奇技淫巧：对于点对(x,y)，将x到根的路径上的点打上标记，查询y到根的路径上有多少标记，最终结果就是dep(lca)；

题目要求的式子中i是从（1，x），根据上面的性质，我们可以想到把1∼x的点都这样打上标记，再来查询。

对于每种询问，我们进行的是相同操作，只是查询时间不同，所以考虑将询问离线，从1∼n依次打标记，每次打完标记，如果当前有查询就查询。

对于打标记和查询可以看出就是链修改和链查询，所以空调用树链剖分。

那么k≠1呢，考虑何时上面的思路，要怎么给x到根路径上的点打标记，才能使得y查询出来是dep(lca)k;

很容易想到给深度为i的点标记为ik\-(i-1)k，这样查询出来中间一些东西抵消掉最终就是dep(lca)k;

性质问题就变成了，链修改是每个点药改的权值不同，怎么改？

可以看到虽然要改的权值不同，但每次一个点要改的权值是固定的，所以对于每个点记录他的基础权值base，每次修改下传修改次数val，对于这个点权值的影响就是val\*base;

这样就能很好地解决这个问题，要注意的是，建树时base也要update。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//思路：对于本题，求dep[lca(x,y)],在根到x的路径上的点的权值++,最后查询y到根的权值和就是ans
    //至于dep^k，就在深度为d的点权值+d^k-(d-1)^k 
    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int maxn=50005;
    const int mod=998244353;
    int n,m,k;
    int fa[maxn],son[maxn],size[maxn],dep[maxn];
    int num,id[maxn],top[maxn],a[maxn];
    int root,ls[maxn<<1],rs[maxn<<1];
    ll sum[maxn<<1],base[maxn<<1],tag[maxn<<1];
    ll get_it[maxn];//ans 
    vector<int> e[maxn];
    vector<pair<int,int> >q[maxn];
    
    template<class T>void read(T &x){
        x=0;char ch=getchar();
        while(!isdigit(ch)) ch=getchar();
        while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    }
    
    ll fpow(ll a,ll b){
        ll ans=1;
        while(b){
            if(b&1) ans=ans*a%mod;
            a=a*a%mod;
            b>>=1;
        }
        return ans;
    }
    
    void dfs(int u){
        size[u]=1;
        for(unsigned int i=0;i<e[u].size();i++){
            int v=e[u][i];
            dep[v]=dep[u]+1;
            dfs(v);
            size[u]+=size[v];
            if(size[son[u]]<size[v]) son[u]=v;
        }
    }
    
    void dfs(int u,int tp){
        id[u]=++num;
        a[num]=dep[u];
        top[u]=tp;
        if(!son[u]) return ;
        dfs(son[u],tp);
        for(unsigned int i=0;i<e[u].size();i++){
            int v=e[u][i];
            if(v==son[u]) continue;
            dfs(v,v);
        }
    }
    
    void update(int rt){
        base[rt]=(base[ls[rt]]+base[rs[rt]])%mod;
        sum[rt]=(sum[ls[rt]]+sum[rs[rt]])%mod;
    }
    
    void build(int &rt,int l,int r){
        rt=++num;
        if(l==r){
            base[rt]=((fpow(a[l],k)-fpow(a[l]-1,k))%mod+mod)%mod;
            return ;
        }
        int mid=(l+r)>>1;
        build(ls[rt],l,mid);
        build(rs[rt],mid+1,r);
        update(rt);
    }
    
    void put_tag(int rt,int val){
        tag[rt]+=val;
        if(tag[rt]>=mod) tag[rt]-=mod;
        sum[rt]=(sum[rt]+base[rt]*val%mod)%mod;
    }
    
    void push_down(int rt){
        put_tag(ls[rt],tag[rt]);
        put_tag(rs[rt],tag[rt]);
        tag[rt]=0;
    }
    
    void modify(int rt,int l,int r,int a_l,int a_r){
        if(a_l<=l&&r<=a_r){
            put_tag(rt,1);
            return ;
        }
        if(tag[rt]) push_down(rt);
        int mid=(l+r)>>1;
        if(a_l<=mid) modify(ls[rt],l,mid,a_l,a_r);
        if(mid<a_r) modify(rs[rt],mid+1,r,a_l,a_r);
        update(rt);
    }
    
    void modify(int x,int y){
        while(top[x]!=top[y]){
            modify(1,1,n,id[top[y]],id[y]);
            y=fa[top[y]];
        }
        modify(1,1,n,id[x],id[y]);
    }
    
    ll query(int rt,int l,int r,int a_l,int a_r){
        if(a_l<=l&&r<=a_r) return sum[rt];
        if(tag[rt]) push_down(rt);
        int mid=(l+r)>>1;
        ll ret=0;
        if(a_l<=mid) ret+=query(ls[rt],l,mid,a_l,a_r);
        if(mid<a_r) ret+=query(rs[rt],mid+1,r,a_l,a_r);
        return ret%mod;
    }
    
    ll query(int x,int y){
        ll ret=0;
        while(top[x]!=top[y]){
            ret=(ret+query(1,1,n,id[top[y]],id[y]))%mod;
            //printf("%d %d ",id[top[y]],id[y]);
            y=fa[top[y]]; 
        }
        ret=(ret+query(1,1,n,id[x],id[y]))%mod;
        //printf("%d %d\n",id[x],id[y]);
        return ret;
    }
    
    int main(){
        read(n);read(m);read(k);
        for(int i=2;i<=n;i++){
            read(fa[i]);
            e[fa[i]].push_back(i);
        }
        for(int i=1;i<=m;i++){
            int x,y;
            read(x);read(y);
            q[x].push_back(make_pair(y,i));
        }
        dep[1]=1;
        dfs(1);
        dfs(1,1);
        num=0;
        build(root,1,n);
        for(int i=1;i<=n;i++){
            modify(1,i);
            for(unsigned int j=0;j<q[i].size();j++)
             get_it[q[i][j].second]=query(1,q[i][j].first);
        }
        for(int i=1;i<=m;i++) printf("%lld\n",get_it[i]);
    }

转载于:https://www.cnblogs.com/sto324/p/11247041.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/65f897e5e89348669188e6b7188bea4c.png