题目链接

题解

当查询a b k时, 其结果是: 所有ab简单路径上的点i的Depth[ i] * k 之和, (将这个值, 看成是 点权)
也就是: 树上点权的 前缀和.

预处理: Sum[ N_][ K_], 则Sum[ i][ j]为: i到树根, 所有的Depth[ j] * k的和.

代码

#include 
//----
#define  LITERAL_  static constexpr
#define  GET_( _t, _i)  ::std::get< _i>( _t)
#define  PAR_( _type, _name)  const _type & _name
#define  IS_IN_RANGE_( _c, _l, _r)  ( ( (_c) >= (_l)) && ( (_c) <= (_r)))
#define  FOR_( _i, _l, _r, _s)  for( int _i = _l; _i <= _r; _i += _s)
#define  FOR_RE_( _i, _l, _r, _s)  for( int _i = _l; _i >= _r; _i -= _s)
//--
#ifdef  SUPIMO_DEBUG_
  #define DEBUG_( ...)  __Debug( __VA_ARGS__, __LINE__)
#else
  #define DEBUG_( ...)  ( void)0
#endif
//--
using namespace ::std;
using Ll_ = long long;
//--
bool __Debug_is_first = true;
template< class _Last>
void __Debug( _Last _last){
    if( __Debug_is_first){
        cout << "(Debug) ";
        __Debug_is_first = false;
    }
    cout << " [Line: " << _last << "]" << endl;
    __Debug_is_first = true;
}
template< class _Head, class ... _Other>
void __Debug( _Head _head, _Other ... _other ){
    if( __Debug_is_first){
        cout << "(Debug) ";
        __Debug_is_first = false;
    }
    cout << _head << ", ";
    __Debug( _other ...);
}
//----
LITERAL_ int N_ = int( 3e5) + 5;
LITERAL_ int K_ = int( 50) + 5;
LITERAL_ int Mod_ = 998244353;
LITERAL_ int Root_ = 1;
int N, M; //< (点数) (查询数) (根)
int Head[ N_], Ver[ N_ * 2], Nex[ N_ * 2], Edges;
int Log[ N_]; //< Log[ a] = b;  2^b <= a, 最大的b
int Depth[ N_], Fa[ N_][ 21];
int Sum[ N_][ K_]; //< 树上前缀和, 树根为前缀和的起点; Sum[ i][ j]为: i到Root_所有点的 `depth^j` 的之和
//--
void Init_graph(){
    Edges = 0;
    memset( Head, -1, sizeof( Head));
}
void Add_edge( PAR_( int, _a), PAR_( int , _b)){
    Ver[ Edges] = _b;
    Nex[ Edges] = Head[ _a];
    Head[ _a] = Edges;
    ++ Edges;
}
void Dfs_lca( PAR_( int, _cur), PAR_( int, _fa)){
    for( int nex, i = Head[ _cur]; ~i; i = Nex[ i]){
        nex = Ver[ i];
        if( nex != _fa){
            Depth[ nex] = Depth[ _cur] + 1;
            //--
            Fa[ nex][ 0] = _cur;
            FOR_( step, 1, Log[ Depth[ nex]], 1){
                Fa[ nex][ step] = Fa[ Fa[ nex][ step - 1]][ step - 1];
//                DEBUG_( nex, step, Fa[ nex][ step]);
            }
            //--
            Dfs_lca( nex, _cur);
        }
    }
}
void Build_lca(){
    { //* build `Log`
        FOR_( i, 1, N, 1){
            if( 1 == i){
                Log[ 1] = 0;
            }
            else{
                if( ( 1 << ( Log[ i - 1] + 1)) == i){
                    Log[ i] = Log[ i - 1] + 1;
                }
                else{
                    Log[ i] = Log[ i - 1];
                }
            }
        }
    }
    //--
    Depth[ Root_] = 0;
    Dfs_lca( Root_, -1);
}
int Lca( PAR_( int, _a), PAR_( int, _b)){
    int low = _a, hig = _b;
    if( Depth[ low] < Depth[ hig]){
        swap( low, hig);
    }
    while( Depth[ low] != Depth[ hig]){
        low = Fa[ low][ Log[ Depth[ low] - Depth[ hig]]];
    }
    if( low == hig){ //< 如果不判断, 假如low=Root, 则下面代码中的Log[ 0]是个未定义行为
        return low;
    }
    FOR_RE_( i, Log[ Depth[ low]], 0, 1){ //< not `Log[ low]`
        if( Fa[ low][ i] != Fa[ hig][ i]){
            low = Fa[ low][ i];
            hig = Fa[ hig][ i];
        }
    }
    assert( Fa[ low][ 0] == Fa[ hig][ 0]);
    return Fa[ low][ 0];
}
void Dfs_sum( PAR_( int, _cur), PAR_( int, _fa)){
    for( int nex, i = Head[ _cur]; ~i; i = Nex[ i]){
        nex = Ver[ i];
        if( nex != _fa){
            Ll_ val = 1;
            FOR_( i, 1, K_ - 1, 1){
                val = val * Depth[ nex] % Mod_;
                Sum[ nex][ i] = ( Ll_( Sum[ _cur][ i]) + val) % Mod_;
//                DEBUG_( nex, i, Sum[ nex][ i]);
            }
            //--
            Dfs_sum( nex, _cur);
        }
    }
}
void Build_sum(){
    FOR_( i, 1, K_ - 1, 1){
        Sum[ Root_][ i] = 0; //< 0^i = 0
    }
    Dfs_sum( Root_, -1);
}
void __Solve(){
    Init_graph();
    scanf("%d", &N);
    FOR_( i, 1, N-1, 1){
        int a, b;
        scanf("%d%d", &a, &b);
        Add_edge( a, b);
        Add_edge( b, a);
    }
    Build_lca();
    Build_sum();
    scanf("%d", &M);
    FOR_( i, 1, M, 1){
        int a, b, k;
        scanf("%d%d%d", &a, &b, &k);
        int lca = Lca( a, b);
        int fa_lca = ( lca == Root_ ? -1 : Fa[ lca][ 0]);
        Ll_ ans = Ll_( Sum[ a][ k]) + Sum[ b][ k] - Sum[ lca][ k];
        if( fa_lca != -1){
            ans -= Sum[ fa_lca][ k];
        }
        ans = ( ans % Mod_ + Mod_) % Mod_;
        printf("%lld\n", ans);
    }
}
//--
int main(){
    //--
    int tests = 1;
    // scanf("%d", &tests);
    for( int i = 0; i < tests; ++i){
        __Solve();
    }
    return 0;
}

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171