树上前缀和

设sum[i]表示节点i到根节点的权值总和。
如果是点权,x,y路径上的和为sum[x]+sum[y]-sum[lca]-sum[fa[lca]]
如果是边权,x,y路径上的和为sum[x]+sum[y]-2*sum[lca]

边前缀和例题Loj #10134.Dis

#include <bits/stdc++.h>
using namespace std;

const int N = 1e4+5;

int n , m , sum[N] , logN , dep[N] , fa[N][15];
vector<pair<int,int>> e[N];

int read(){
    int x = 0 , f = 1 , ch = getchar();
    while( (ch < '0' || ch > '9') && ch != '-' ) ch = getchar();
    if( ch == '-' ) f = -1 , ch = getchar();
    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();
    return x * f;
}

void dfs( int x ){
    for( auto [v,w] : e[x] ){
        if( dep[v] ) continue;
        dep[v] = dep[x] + 1 , fa[v][0] = x , sum[v] = sum[x] + w;
        for( int i = 1 ; i <= logN ; i ++ )
            fa[v][i] = fa[ fa[v][i-1] ][ i-1 ];
        dfs(v);
    }
}

int lca( int x , int y ){
    if( dep[x] > dep[y] ) swap( x , y );
    for( int i = logN ; i >= 0 ; i -- )
        if( dep[ fa[y][i] ] >= dep[x] ) y = fa[y][i];
    if( x == y ) return x;
    for( int i = logN ; 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 = read() , m = read() ,logN = (int)log2(n)+1;
    for( int i = 2 , u , v , w ; i <= n ; i ++ )
        u = read() , v = read() , w = read() , e[u].push_back( {v,w} ) , e[v].push_back( {u,w} );
    dep[1] = 1 , dfs(1);
    for( int u , v ; m ; m -- ){
        u = read() , v = read();
        cout << sum[u] + sum[v] - 2 * sum[ lca(u,v) ] << "\n";
    }
}

点前缀和例题Luogu P4427

// Loj 2491
// 一颗树根节点是 1 , 点权就是深度的 k 次方
// m次询问,每次问(u,v)路径上点权之和
// k 每次都不同但是取值范围只有[1,50]
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 3e5+5 , mod = 998244353;
int n , sum[N][55] , fa[N][20] , dep[N] , logN;
vector<int> e[N];

int read(){
    int x = 0 , f = 1 , ch = getchar();
    while( (ch < '0' || ch > '9') && ch != '-' ) ch = getchar();
    if( ch == '-' ) f = -1 , ch = getchar();
    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();
    return x * f;
}

void dfs( int x ){
    for( auto v : e[x] ){
        if( v == fa[x][0] ) continue;
        dep[v] = dep[x] + 1 , fa[v][0] = x;
        for( int i = 1 , val = 1; i <= 50 ; i ++ )
            val = val * dep[v]% mod , sum[v][i] = (val + sum[x][i]) % mod;
        for( int i = 1 ; i <= logN ; i ++ )
            fa[v][i] = fa[ fa[v][i-1] ][i-1];
        dfs(v);
    }
}

int lca( int x , int y ){
    if( dep[x] > dep[y] ) swap( x , y );
    for( int i = logN ; i >= 0 ; i -- )
        if( dep[ fa[y][i] ] >= dep[x] ) y = fa[y][i];
    if( x == y ) return x;
    for( int i = logN ; i >= 0 ; i -- )
        if( fa[x][i] != fa[y][i] ) x = fa[x][i] , y = fa[y][i];
    return fa[x][0];
}

int32_t main(){
    n = read() , logN = (int)log2(n)+1;
    for( int i = 2 , u , v ; i <= n ; i ++ )
        u = read() , v = read() , e[u].push_back(v) , e[v].push_back(u);
    dep[1] = 0;
    dfs( 1 );
    for( int m = read() , u , v , k , t ; m ; m -- ){
        u = read() , v = read() , k = read() , t = lca( u , v );
        cout << (sum[u][k]+sum[v][k]-sum[t][k]-sum[fa[t][0]][k]+2*mod)%mod << "\n";
    }
    return 0;
}