juruo求助,样例能过,全部WA(已经加膜数了)
查看原帖
juruo求助,样例能过,全部WA(已经加膜数了)
125018
ztx__楼主2020/8/10 16:09

dalao们能帮我审一下代码吗,实在找不出来我哪里错了qwq

#include <bits/stdc++.h>
using namespace std;
#define MAXN 300005
#define MAXK 55
#define MOD 998244353LL
typedef long long ll;
ll n,m;
vector<ll> g[MAXN];
ll dfn[MAXN],top[MAXN],deep[MAXN],son[MAXN],size[MAXN],step,f[MAXN],deep_pow[MAXN][MAXK];
ll quick_pow(ll x,ll y){
    if(y==0){
        return 1;
    }else if(y%2){
        ll nex=quick_pow(x,y/2);
        return nex*nex*x%MOD;
    }else{
        ll nex=quick_pow(x,y/2);
        return nex*nex%MOD;
    }
}
void dfs1(ll u,ll fa){
    f[u]=fa;
    deep[u]=deep[fa]+1;
    size[u]=1;
    for(ll i=0;i<g[u].size();i++){
        ll v=g[u][i];
        if(v!=fa){
            dfs1(v,u);
            size[u]+=size[v];
            if(size[son[u]]<size[v]){
                son[u]=v;
            }
        }
    }
}
void dfs2(ll u,ll tp){
    top[u]=tp;
    dfn[u]=++step;
    if(son[u]){
        dfs2(son[u],tp);
        for(ll i=0;i<g[u].size();i++){
            ll v=g[u][i];
            if(son[u]!=v&&v!=f[u]){
                dfs2(v,v);
            }
        }
    }
}
ll LCA(ll u,ll v){
    while(top[u]!=top[v]){
        if(deep[top[u]]<deep[top[v]]){
            swap(u,v);
        }
        u=f[top[u]];
    }
    if(deep[u]>deep[v]){
        swap(u,v);
    }
    return u;
}
void dfs3(ll u,ll k){
    deep_pow[u][k]=(quick_pow(deep[u],k)+deep_pow[f[u]][k])%MOD;
    for(ll i=0;i<g[u].size();i++){
        ll v=g[u][i];
        if(v!=f[u]){
            dfs3(v,k);
        }
    }
}
int main(){
    scanf("%lld",&n);
    for(ll i=1;i<=n-1;i++){
        ll u,v;
        scanf("%lld%lld",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    scanf("%lld",&m);
    deep[0]=-1;
    dfs1(1,0);
    dfs2(1,1);
    for(ll i=0;i<=50;i++){
        dfs3(1,i);
    }
    for(ll i=1;i<=m;i++){
        ll u,v,k;
        scanf("%lld%lld%lld",&u,&v,&k);
        ll lca=LCA(u,v);
        printf("%lld\n",(deep_pow[u][k]
                         +deep_pow[v][k]
                         -deep_pow[lca][k]
                         -deep_pow[f[lca]][k]
                         +MOD)
                         %MOD);
    }
    return 0;
}
2020/8/10 16:09
加载中...