master 对树上的求和非常感兴趣。他生成了一棵有根树，并且希望多次询问这棵树上一段路径上所有节点深度的k
次方和，而且每次的k 可能是不同的。此处节点深度的定义是这个节点到根的路径上的边数。他把这个问题交给
了pupil，但pupil 并不会这么复杂的操作，你能帮他解决吗？
因为这个k很小，所以就是个树上差分板子
预处理出深度之后弄个树上前缀和（对于不同的k暴力存就好，因为k最大50）
预处理复杂度是$O(nk)$的
然后每次询问的答案其实就是两个点的前缀和减掉他们的$LCA$的前缀和再加上他们的$LCA$的k次方
#include <bits/stdc++.h> using namespace std ; #define N 300010 #define mod 998244353 #define inf 0x3f3f3f3f #define ll long long int n , m ; int dep[ N ] , siz[ N ] , top[ N ] , fa[ N ] ; int head[ N ] , cnt ; ll c[ N ][ 60 ] ; struct node { int to , nxt ; } e[ N << 1 ] ; void ins( int u , int v ) { e[ ++ cnt ].to = v ; e[ cnt ].nxt = head[ u ] ; head[ u ] = cnt ; } void dfs1( int u ) { siz[ u ] = 1 ; for( int i = head[ u ] ; i ; i = e[ i ].nxt ) { int v = e[ i ].to ; if( v == fa[ u ] ) continue ; fa[ v ] = u ; dep[ v ] = dep[ u ] + 1 ; dfs1( v ) ; siz[ u ] += siz[ v ] ; } } void dfs2( int u , int topf ) { top[ u ] = topf ; int k = 0 ; for( int i = head[ u ] ; i ; i = e[ i ].nxt ) { if( e[ i ].to != fa[ u ] && siz[ e[ i ].to ] > siz[ k ] ) k = e[ i ].to ; } if( !k ) return ; dfs2( k , topf ) ; for( int i = head[ u ] ; i ; i = e[ i ].nxt ) { if( e[ i ].to != k && e[ i ].to != fa[ u ] ) dfs2( e[ i ].to , e[ i ].to ) ; } } void dfs3( int u ) { ll x = 1 ; for( int k = 1 ; k <= 50 ; k ++ ) { x = 1ll * x * dep[ u ] % mod ; c[ u ][ k ] = ( 1ll * c[ fa[ u ] ][ k ] + x ) % mod ; } for( int i = head[ u ] ; i ; i = e[ i ].nxt ) { if( e[ i ].to == fa[ u ] ) continue ; dfs3( e[ i ].to ) ; } } int lca( int x , int y ) { while( top[ x ] != top[ y ] ) { if( dep[ top[ x ] ] < dep[ top[ y ] ] ) swap( x , y ) ; x = fa[ top[ x ] ] ; } if( dep[ x ] > dep[ y ] ) swap( x , y ) ; return x ; } ll power( ll a , ll b ) { ll ans = 1 , base = a ; while( b ) { if( b&1 ) ans = ans * base % mod ; base = base * base % mod ; b >>= 1 ; } return ans % mod ; } int main() { scanf( "%d" , &n ) ; for(int i = 1 , u , v ; i < n ; i ++ ) { scanf( "%d%d" , &u , &v ) ; ins( u , v ) ; ins( v , u ) ; } dfs1( 1 ) ; dfs2( 1 , 1 ) ; dfs3( 1 ) ; scanf( "%d" , &m ) ; while( m -- ) { int u , v , k ; scanf( "%d%d%d" , &u , &v , &k ) ; int l = lca( u , v ) ; printf( "%lld\n" , ( c[ u ][ k ] % mod + c[ v ][ k ] % mod - 2 * c[ l ][ k ] % mod + power( dep[ l ] , k ) + mod ) % mod ) ; } return 0 ; }
原文：https://www.cnblogs.com/henry-1202/p/BZOJ5293.html