CF1467D Sum of Paths

设 dp_{i, j} 表示经过 j 步移动之后，停留在 i 上第方案数。

易得动态转移方程 dp_{i,j}=dp_{i-1, j-1} + dp_{i + 1, j - 1} 需判断边界。

同时我们发现 dp_{i,j} 还表示移动 j 步恰好到 i 到方案数。

设 a_{i, j} 表示长度为 k 的合法路径在第 j 步落在了的 i 的位置上。

我们得到 a_{i,j} = dp_{i, j} * dp_{i, k - j}

设 cnt_i 表示下标为 a_i 对答案的贡献。

易知 cnt_i = \sum_{j=0}^n a_{i, j}

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
#define int long long
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int N = 5e3 + 5, mod = 1e9 + 7;
int v[N], dp[N][N], a[N][N], cnt[N];
int positive(int x) {
    return (x % mod + mod) % mod;
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int n = rd(), k = rd(), q = rd();
    for(int i = 1; i <= n; i++) v[i] = rd();
    for(int i = 1; i <= n; i++) { 
        dp[i][0] = 1;
    }

    for(int i = 1; i <= k; i++) {
        for(int j = 1; j <= n; j++) {
            if(j - 1 >= 1) dp[j][i] = (dp[j][i] + dp[j - 1][i - 1]) % mod;
            if(j + 1 <= n) dp[j][i] = (dp[j][i] + dp[j + 1][i - 1]) % mod;
        }
    }

//  for(int i = 0; i <= k; i++) {
//      for(int j = 1; j <= n; j++) 
//          cout << dp[j][i] << " ";
//      cout << endl;
//  }
//  cout << endl;

    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= k; j++) {
            a[i][j] = dp[i][j] * dp[i][k - j] % mod;
        }
    }

//  for(int i = 1; i <= n; i++) {
//      for(int j = 0; j <= k; j++) 
//          cout << a[i][j] << " ";
//      cout << endl;
//  }
//  cout << endl;

    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= k; j++) {
            cnt[i] = (cnt[i] + a[i][j]) % mod;
        }
    }

//  for(int i = 1; i <= n; i++) 
//      cout << cnt[i] << " ";
//  cout << endl;

    int ans = 0;
    for(int i = 1; i <= n; i++) {
        ans = (ans + v[i] * cnt[i] % mod) % mod;
    }
    ans = positive(ans);

    for(int i = 1; i <= q; i++) {
        int u = rd(), x = rd();
        ans += (x - v[u]) * cnt[u];
        v[u] = x;
        ans = positive(ans);
        printf("%lld\n", ans);
    }

    return 0;
}

P3899 谈笑风生

树上主席树。按照dfs序创建版本。

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
#define int long long
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int N = 3e5 + 5, M = 3e5 + 5;

struct Edge {
    int to, nxt;
} Edge[M << 1];

int head[N], cnt;

void addEdge(int u, int v) {
    Edge[++cnt].to = v;
    Edge[cnt].nxt = head[u];
    head[u] = cnt;
}

int dep[N], dfn[N], sz[N], idx, id[N];

void dfs1(int u, int fa, int depth) {
    dep[u] = depth; dfn[u] = ++idx; id[idx] = u; sz[u] = 1;
    for(int i = head[u]; i; i = Edge[i].nxt) {
        const int v = Edge[i].to;
        if(v == fa) continue;
        dfs1(v, u, depth + 1);
        sz[u] += sz[v];
    }
}

class SegmentTree {
#define MID int mid = (l + r) >> 1
#define lson l, mid, node[x].ls
#define rson mid + 1, r, node[x].rs
public :
    static const int N = ::N;
    struct Node {
        int ls, rs, sum;
        Node() : ls(0), rs(0), sum(0) { }
    } node[N * 65];

    int root[N], cnt;

    SegmentTree() : cnt(0) { }

    int build(int l, int r) {
        int x = ++cnt;
        if(l == r) {
            node[x].ls = node[x].rs = 0;
            node[x].sum = 0;
            return x;
        }
        MID;
        node[x].ls = build(l, mid);
        node[x].rs = build(mid + 1, r);
        push_up(x);
        return x;
    }

    void push_up(int x) {
        node[x].sum = node[node[x].ls].sum + node[node[x].rs].sum;
    }

    int clone(int x) {
        node[++cnt] = node[x];
        return cnt;
    }

    void modify_add(int l, int r, int &x, int p, int v) {
        x = clone(x);
        if(l == r) {
            node[x].sum += v;
            return ;
        }
        MID; 
        if(p <= mid) modify_add(lson, p, v);
        if(p > mid)  modify_add(rson, p, v);
        push_up(x);
    }

    int query(int l, int r, int x, int p, int q) {
        if(p <= l && r <= q) 
            return node[x].sum;

        MID; 
        int res = 0;
        if(p <= mid) res += query(lson, p, q);
        if(q > mid)  res += query(rson, p, q);
        return res;
    }

} st;

signed main() {
#ifdef LOCAL
    file();
#endif
    int n = rd(), q = rd();
    for(int i = 1; i < n; i++) {
        int u = rd(), v = rd();
        addEdge(u, v); addEdge(v, u);
    }

    st.root[0] = st.build(1, n);
    dfs1(1, 1, 1);
    for(int i = 1; i <= n; i++) {
        int u = id[i];
        st.root[i] = st.root[i - 1];
        st.modify_add(1, n, st.root[i], dep[u], sz[u] - 1);
    }

    for(int i = 1; i <= q; i++) {
        int p = rd(), k = rd();
        int ans = 0;
        ans += min(k, dep[p] - 1) * (sz[p] - 1);
        ans += st.query(1, n, st.root[dfn[p] + sz[p] - 1], dep[p] + 1, dep[p] + k);
        ans -= st.query(1, n, st.root[dfn[p]], dep[p] + 1, dep[p] + k);
        printf("%lld\n", ans);
    }

    return 0;
}