救救孩子!!

回复帖子

@__皮娃__ 2019-09-16 13:45 回复

30分AC134求助

#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <string>
#include <bitset>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iostream>
#include <algorithm>
using namespace std;

template <typename Type>
inline int read(Type& x) {
    x = 0;
    char c = getchar(), f = 1;
    for (; c > '9' || c < '0'; c = getchar())
        if (c == -1)
            return -1;
        else if (c == '-')
            f = -f;
    for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    x *= f;
    return 1;
}
template <typename Type>
inline int write(Type x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x / 10)
        return write(x / 10) && putchar(x % 10 | 48);
    return putchar(x | 48);
}
template <typename Type>
inline int write(Type x, char c) { return write(x) && putchar(c); }
#define Min(a, b) (a < b ? a : b)
#define Max(a, b) (a > b ? a : b)

#define MAXN 100005
int n, q, root, mod;
long long val[MAXN];
struct edge {
    int v, nxt;
    inline edge() { }
} e[MAXN << 1];
int tot, f[MAXN];
inline void addEdge(int u, int v) {
    tot++;
    e[tot].v = v, e[tot].nxt = f[u], f[u] = tot;
}
int fa[MAXN], dep[MAXN], siz[MAXN], son[MAXN], tp[MAXN], id[MAXN], rnk[MAXN], cnt;
inline void dfs1(int x, int fat, int d) {
    dep[x] = d, siz[x] = 1, fa[x] = fat;
    for(int i = f[x]; ~i; i = e[i].nxt) {
        int v = e[i].v;
        if(v == fat) continue;
        dfs1(v, x, d + 1);
        siz[x] += siz[v];
        if(siz[son[x]] < siz[v]) son[x] = v;
    }
}
inline void dfs2(int x, int fa, int fnt) {
    tp[x] = fnt, id[x] = ++cnt, rnk[cnt] = x;
    if(!son[x]) return ;
    dfs2(son[x], x, fnt);
    for(int i = f[x]; ~i; i = e[i].nxt) {
        int v = e[i].v;
        if(v != fa && v != son[x]) dfs2(v, x, v);
    }
}
inline void init(int root) {
    memset(fa, 0, sizeof fa);
    memset(dep, 0, sizeof dep);
    memset(siz, 0, sizeof siz);
    memset(son, 0, sizeof son);
    memset(tp, 0, sizeof tp);
    memset(id, 0, sizeof id);
    memset(rnk, 0, sizeof rnk);
    cnt = 0;
    dfs1(root, -1, 0);
    dfs2(root, -1, root);
}
struct SegmentTree {
    struct segment {
        int l, r;
        long long val, laz;
        inline segment() { }
    } tr[MAXN << 2];
    inline int ls(int x) { return x << 1; }
    inline int rs(int x) { return x << 1 | 1; }
    inline int dist(int p) { return tr[p].r - tr[p].l + 1; }
    inline void build(int p, int l, int r) {
        tr[p].l = l, tr[p].r = r;
        if(l == r) { tr[p].val = val[rnk[l]] % mod; return ; }
        int mid = (l + r) >> 1;
        build(ls(p), l, mid);
        build(rs(p), mid + 1, r);
        tr[p].val = (tr[ls(p)].val + tr[rs(p)].val) % mod;
    }
    inline void build(int l, int r) { build(1, l, r); }
    inline void lazy(int p) {
        if(!tr[p].laz || tr[p].l == tr[p].r) return ;
        tr[ls(p)].val = (tr[ls(p)].val + tr[p].laz * dist(ls(p)) % mod) % mod;
        tr[rs(p)].val = (tr[rs(p)].val + tr[p].laz * dist(rs(p)) % mod) % mod;
        tr[ls(p)].laz = (tr[ls(p)].laz + tr[p].laz) % mod;
        tr[rs(p)].laz = (tr[rs(p)].laz + tr[p].laz) % mod;
        tr[p].laz = 0;
    }
    inline void update(int p, int l, int r, long long val) {
        if(l <= tr[p].l && tr[p].r <= r) {
            tr[p].val = (tr[p].val + val * dist(p)) % mod, tr[p].laz = (tr[p].laz + val) % mod;
            return ;
        }
        if(tr[p].r < l || r < tr[p].l) return ;
        lazy(p);
        update(ls(p), l, r, val); update(rs(p), l, r, val);
        tr[p].val = (tr[ls(p)].val + tr[rs(p)].val) % mod;
    }
    inline void update(int l, int r, long long val) { update(1, l, r, val); }
    inline long long query(int p, int l, int r) {
        if(l <= tr[p].l && tr[p].r <= r)
            return tr[p].val % mod;
        if(tr[p].r < l || r < tr[p].l) return 0;
        lazy(p);
        long long vall = query(ls(p), l, r),
                  valr = query(rs(p), l, r);
        return (vall + valr) % mod;
    }
    inline long long query(int l, int r) { return query(1, l, r) % mod; }
} tr;
namespace TreeLinkDivide {
    bool built = 0;
    inline long long sum(int x, int y) {
        if(!built) tr.build(1, n);
        built = 1;
        long long ans = 0, fx = tp[x], fy = tp[y];
        while(fx != fy) {
            if(dep[fx] > dep[fy]) {
                ans = (ans + tr.query(id[x], id[fx])) % mod;
                x = fa[fx], fx = tp[x];
            }
            else {
                ans = (ans + tr.query(id[y], id[fy])) % mod;
                y = fa[fy], fy = tp[y];
            }
        }
        if(id[x] > id[y]) ans = (ans + tr.query(id[y], id[x]))% mod;
        else ans = (ans + tr.query(id[x], id[y])) % mod;
        return ans;
    }
    inline void update(int x, int y, long long val) {
        if(!built) tr.build(1, n);
        built = 1;
        long long fx = tp[x], fy = tp[y];
        while(fx != fy) {
            if(dep[fx] > dep[fy]) {
                tr.update(id[x], id[fx], val);
                x = fa[fx], fx = tp[x];
            }
            else {
                tr.update(id[y], id[fy], val);
                y = fa[fy], fy = tp[y];
            }
        }
        if(id[x] > id[y]) tr.update(id[y], id[x], val);
        else tr.update(id[x], id[y], val);
    }
    inline long long sumson(int x) {
        if(!built) tr.build(1, n);
        built = 1;
        return tr.query(id[x], id[x] + siz[x] - 1) % mod;
    }
    inline void updateson(int x, long long val) {
        if(!built) tr.build(1, n);
        built = 1;
        tr.update(id[x], id[x] + siz[x] - 1, val);
    }
}
using namespace TreeLinkDivide;

int main() {
    read(n), read(q), read(root), read(mod);
    for(int i = 1; i <= n; i++)
        read(val[i]);
    memset(f, -1, sizeof f);
    for(int i = 1, u, v; i < n; i++)
        read(u), read(v), addEdge(u, v), addEdge(v, u);
    init(root);
    for(int i = 1; i <= q; i++) {
        int ty; read(ty);
        int x, y; long long z;
        if(ty == 1) read(x), read(y), read(z), update(x, y, z);
        else if(ty == 2) read(x), read(y), write(sum(x, y), '\n');
        else if(ty == 3) read(x), read(z), updateson(x, z);
        else read(x), write(sumson(x), '\n');
    }
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。