题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=5293
k<=50
所以预处理一下，然后求一个前缀和就好了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include<bits/stdc++.h> #define MAXN 300030 #define ll long long #define mod 998244353 #define pb push_back using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } int n,m; int fa[MAXN][19],deep[MAXN]; ll sum[MAXN][55]; vector<int>go[MAXN]; void dfs(int x){ sum[x][0]=1; for(int i=1; i<=50; i++)sum[x][i]=sum[x][i-1]*(ll)deep[x]%mod; for(int i=0; i<=50; i++)sum[x][i]=(sum[x][i]+sum[fa[x][0]][i])%mod; for(int i=1; i<=18; i++)fa[x][i]=fa[fa[x][i-1]][i-1]; for(int i=0; i<go[x].size(); i++){ int to=go[x][i]; if(to==fa[x][0])continue; fa[to][0]=x; deep[to]=deep[x]+1; dfs(to); } } inline int lca(int x,int y){ if(deep[x]<deep[y])swap(x,y); for(int i=18; i>=0; i--)if(deep[x]-deep[y]>=(1<<i))x=fa[x][i]; if(x==y)return x; for(int i=18; i>=0; i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; return fa[x][0]; } int main(){ n=rd(); for(int i=1; i<n; i++){ int x=rd(),y=rd(); go[x].pb(y); go[y].pb(x); } deep[1]=0; dfs(1); m=rd(); while(m--){ int x=rd(),y=rd(),k=rd(); int z=lca(x,y); printf("%lld\n",(sum[x][k]+sum[y][k]-sum[z][k]+mod-sum[fa[z][0]][k]+mod)%mod); } return 0; } |