[BJOI2018]求和

题目大意：
　　一个$n(nle3 imes10^5)$个结点的有根树。$m(mle3 imes10^5)$次询问，每次询问$x,y$路径上所有结点深度$k(kle50)$次方和。
思路：
　　树上前缀和+LCA即可。
 1 #include<cstdio>
 2 #include<cctype>
 3 #include<algorithm>
 4 #include<sys/mman.h>
 5 #include<sys/stat.h>
 6 typedef long long int64;
 7 class MMapInput {
 8     private:
 9         char *buf,*p;
10         int size;
11     public:
12         MMapInput() {
13             register int fd=fileno(stdin);
14             struct stat sb;
15             fstat(fd,&sb);
16             size=sb.st_size;
17             buf=reinterpret_cast<char*>(mmap(0,size,PROT_READ,MAP_PRIVATE,fileno(stdin),0));
18             p=buf;
19         }
20         char getchar() {
21             return (p==buf+size||*p==EOF)?EOF:*p++;
22         }
23 };
24 MMapInput mmi;
25 inline int getint() {
26     register char ch;
27     while(!isdigit(ch=mmi.getchar()));
28     register int x=ch^'0';
29     while(isdigit(ch=mmi.getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
30     return x;
31 }
32 const int N=3e5+1,logN=19,K=51,mod=998244353;
33 int h[N];
34 struct Edge {
35     int to,next;
36 };
37 Edge e[N<<1];
38 inline void add_edge(const int &u,const int &v) {
39     e[++h[0]]=(Edge){v,h[u]};h[u]=h[0];
40     e[++h[0]]=(Edge){u,h[v]};h[v]=h[0];
41 }
42 int dep[N]={-1},anc[N][logN],sum[N][K];
43 inline int log2(const float &x) {
44     return ((unsigned&)x>>23&255)-127;
45 }
46 void dfs(const int &x,const int &par) {
47     dep[x]=dep[anc[x][0]=par]+1;
48     for(register int i=1,v=dep[x];i<K;i++) {
49         sum[x][i]=(sum[par][i]+v)%mod;
50         v=(int64)v*dep[x]%mod;
51     }
52     for(register int i=1;i<=log2(dep[x]);i++) {
53         anc[x][i]=anc[anc[x][i-1]][i-1];
54     }
55     for(int i=h[x];i;i=e[i].next) {
56         const int &y=e[i].to;
57         if(y==par) continue;
58         dfs(y,x);
59     }
60 }
61 inline int lca(int x,int y) {
62     if(dep[x]!=dep[y]) {
63         if(dep[x]<dep[y]) std::swap(x,y);
64         for(register int i=log2(dep[x]-dep[y]);~i;i--) {
65             if(dep[anc[x][i]]>=dep[y]) x=anc[x][i];
66         }
67     }
68     if(x==y) return x;
69     for(register int i=log2(dep[x]);~i;i--) {
70         if(anc[x][i]!=anc[y][i]) {
71             x=anc[x][i];
72             y=anc[y][i];
73         }
74     }
75     return anc[x][0];
76 }
77 inline int query(const int &x,const int &y,const int &k) {
78     const int z=lca(x,y);
79     return ((sum[x][k]+sum[y][k]-sum[z][k]-sum[anc[z][0]][k])%mod+mod)%mod;
80 }
81 int main() {
82     const int n=getint();
83     for(register int i=1;i<n;i++) {
84         add_edge(getint(),getint());
85     }
86     dfs(1,0); 
87     for(register int i=getint();i;i--) {
88         const int x=getint(),y=getint(),k=getint();
89         printf("%d
",query(x,y,k));
90     }
91     return 0;
92 }