洛谷P4427 [BJOI2018]求和

12 March 2019 | duanyll | Tags: OI 题解 LCA

好久都没有发过新文章了，水一点题解吧

这道题乍一看好像是数学题，但观察到 $k\leq50$ ,就可以预处理处每个k对应的树上前缀和，就很好办了

// luogu-judger-enable-o2
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

typedef long long int64;
const int MAXN = 300010;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;

class LFS {
   public:
    LFS() {
        memset(head, -1, sizeof head);
        ecnt = 0;
        n = 0;
    }
    LFS(int N) {
        memset(head, -1, sizeof head);
        ecnt = 0;
        n = N;
    }
    void adde(int from, int to, int w) {
        e[ecnt].to = to;
        e[ecnt].w = w;
        e[ecnt].next = head[from];
        head[from] = ecnt++;
    }
    void addde(int a, int b, int w) {
        adde(a, b, w);
        adde(b, a, w);
    }

   protected:
    struct Edge {
        int to, next, w;
    } e[MAXN * 2];
    int head[MAXN];
    int ecnt;
    int n;

   private:
    virtual void dfs(int u, int fa) {
        for (int i = head[u]; i != -1; i = e[i].next) {
            int v = e[i].to;
            if (v != fa) {
                dfs(v, u);
            }
        }
    }
};

int64 pow_mod(int64 a, int64 b) {
    int64 res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b /= 2;
    }
    return res;
}

class LCA : public LFS{
   public:
   	int dep[MAXN];
   	int64 sum[MAXN][51];
    LCA(int n) : LFS(n) {
        memset(dep, -1, sizeof dep);
        memset(sum,0,sizeof sum);
    }
    void pre(int rt = 1) { dfs(rt, 0, 0); }
    int querylca(int a, int b) {
        if (dep[a] > dep[b]) swap(a, b);
        int h = dep[b] - dep[a];
        for (int i = 20; i >= 0; i--) {
            if(h & (1 << i)) {
                b = f[b][i];
            }
        }
        if (a == b) return a;
        for (int i = 20; i >= 0; i--) {
            if (f[a][i] == f[b][i]) continue;
            a = f[a][i];
            b = f[b][i];
        }
        return f[a][0];
    }

   //protected:
    int f[MAXN][22];

   private:
    void dfs(int u, int d, int fa) {
        dep[u] = d;
        f[u][0] = fa;
        for(int i = 1;i<=50;i++){
        	sum[u][i] = sum[fa][i] + pow_mod(d,i);
        	sum[u][i] %= MOD;
        }
        for (int i = 1; i < 21; i++) {
            f[u][i] = f[f[u][i - 1]][i - 1];
        }
        for (int i = head[u]; i != -1; i = e[i].next) {
            int v = e[i].to;
            if (dep[v] == -1) {
                dfs(v, d + 1, u);
            }
        }
    }
};

#include <cctype>
#include <cstdio>

inline int read() {
    int X = 0, w = 0;
    char ch = 0;
    while (!isdigit(ch)) {
        w |= ch == '-';
        ch = getchar();
    }
    while (isdigit(ch)) {
        X = (X << 3) + (X << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -X : X;
}

int main(){
    int n = read();
    LCA* tree = new LCA(n);
    for(int i = 1;i<n;i++){
        int u = read();
        int v = read();
        tree->addde(u,v,1);
    }
    tree->pre();
    int m = read();
    for(int i = 1;i<=m;i++){
        int a = read();
        int b = read();
        int k = read();
        int lca = tree->querylca(a,b);
        cout << ((tree->sum[a][k] + tree->sum[b][k] - tree->sum[lca][k] - tree->sum[tree->f[lca][0]][k])%MOD + MOD)%MOD << endl;
    }
}

要特别注意题目要统计的是点权不是边权，因此小心前缀和重复计算LCA的值。