GZOI2019 旧词

询问按照x从小到大分类。

然后按照x递增处理，每次把根到x的路径上深度为p的点的值加上$p^k-(p-1)^k$。

这样对于任何一条到根深度为p的路径，其权值为$p^k$。

使用树剖+线段树维护。

线段树的每个叶子节点有一个权值$p^k-(p-1)^k$，这个权值不会改变，同时需要维护区间$a_i\times(p_i^k-(p_i-1)^k)$的和。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <inttypes.h>
#define debug(x) std::cout << #x << " = " << x << std::endl;

typedef long long int int_t;

using std::cin;
using std::endl;
using std::cout;

const int_t mod = 998244353;
const int_t LARGE = 5e4;
int_t power(int_t base,int_t index){
    int_t result=1;
    while(index) {
        if(index&1) result=result*base%mod;
        index>>=1;
        base=base*base%mod;
    }
    return result;
}
struct Node{
    int_t begin,end;
    int_t value = 0;
    Node*left=nullptr,*right=nullptr;
    int_t val1=0,val2=0,mark=0;
    Node(int_t begin,int_t end):begin(begin),end(end){}
    
    void add(int_t x){
        mark+=x;
        val1+=x;
        value=(value+val2*x%mod)%mod;
    }
    void pushDown(){
        if(begin!=end){
            left->add(mark);
            right->add(mark);
            mark=0;
        }
    }
    void maintain(){
        if(begin!=end){
            value=(left->value+right->value)%mod;
            val1=left->val1+right->val1;
            val2=(left->val2+right->val2)%mod;
        }
    }
    void add(int_t begin,int_t end,int_t x){
        if(end<this->begin||begin>this->end) return;
        if(this->begin>=begin&&this->end<=end){
            this->add(x);
            return;
        }
        pushDown();
        left->add(begin,end,x);
        right->add(begin,end,x);
        maintain();
    }
    int_t query(int_t begin,int_t end){
        if(end<this->begin||begin>this->end) return 0;
        if(this->begin>=begin&&this->end<=end) return this->value;
        pushDown();
        return (left->query(begin,end)+right->query(begin,end))%mod;
    }
    static Node* build(int_t begin,int_t end,int_t* arr){
        Node* node=new Node(begin,end);
        if(begin!=end){
            int_t mid=(begin+end)/2;
            node->left=build(begin,mid,arr);
            node->right=build(mid+1,end,arr);
        }else{
            node->val2=arr[begin];
        }
        node->maintain();
        return node;
    }
};
Node* root;
int_t n,q,k;
std::vector<int_t> graph[LARGE+1];
int_t depth[LARGE+1],top[LARGE+1],maxChd[LARGE+1],size[LARGE+1];
int_t parent[LARGE+1];
int_t DFSN[LARGE+1],byDFSN[LARGE+1],target[LARGE+1];
void DFS1(int_t vtx,int_t from=0,int_t depth=1){
    parent[vtx]=from,::depth[vtx]=depth;
    size[vtx]=1;
    for(int_t to:graph[vtx]){
        DFS1(to,vtx,depth+1);
        if(size[to]>size[maxChd[vtx]]) maxChd[vtx]=to;
        size[vtx]+=size[to];
    }
}
void DFS2(int_t vtx){
    DFSN[vtx]=++DFSN[0];
    byDFSN[DFSN[vtx]]=vtx;
    target[DFSN[vtx]] = (power(depth[vtx],k) - power(depth[parent[vtx]],k) + mod)%mod;
    if(maxChd[vtx]){
        top[maxChd[vtx]]=top[vtx];
        DFS2(maxChd[vtx]);
    }
    for(int_t to:graph[vtx]) if(to!=maxChd[vtx]){
        top[to]=to;
        DFS2(to);
    }
}
int_t query(int_t v1){
    int_t result=0;
    while(top[v1]){
        result+=root->query(DFSN[top[v1]],DFSN[v1]);
        result%=mod;
        v1=parent[top[v1]];
    }
    return result;
}
void add(int_t v1,int_t val=1){
    while(top[v1]){
        root->add(DFSN[top[v1]],DFSN[v1],val);
        v1=parent[top[v1]];
    }
}
int_t result[LARGE+1];
struct Query{
    int_t prev, z;
    int_t* result;
};
std::vector<Query> querys[LARGE+1];
int main() {
    scanf("%lld%lld%lld",&n,&q,&k);
    for(int_t i=2;i<=n;i++){
        int_t x;
        scanf("%lld",&x);
        graph[x].push_back(i);
    }
    for(int_t i=1;i<=q;i++){
        int_t x,z;
        scanf("%lld%lld",&x,&z);
        querys[x].push_back(Query{x,z,&result[i]});
    }
    DFS1(1);
    top[1]=1;
    DFS2(1);
    #ifdef DEBUG
    for(int_t i=1;i<=n;i++) cout<<"top "<<i<<" = "<<top[i]<<endl;
    #endif
    
    root=Node::build(1,n,target);
    for(int_t i=1;i<=n;i++){
        add(i);
        for(const auto& query:querys[i]){
            *query.result=::query(query.z);
        }
    }
    for(int_t i=1;i<=q;i++){
        printf("%lld\n",result[i]);
    }
    return 0;
}