树剖板子求助
  • 板块学术版
  • 楼主cmll02
  • 当前回复11
  • 已保存回复11
  • 发布时间2020/9/5 12:35
  • 上次更新2023/11/5 13:42:49
查看原帖
树剖板子求助
171487
cmll02楼主2020/9/5 12:35

P3384

这是记录

不知道哪里错了QAQ

求dalao解答%%%

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define T long long
inline void swap(T &x, T &y)
{
    T t = x;
    x = y, y = t;
}
inline T read()
{
    T num = 0; int f = 1; char c = getchar();
    while (c < 48 || c > 57){ if (c == '-')f = -1; c = getchar(); }
    while (c >= 48 && c <= 57)num = num * 10 + (c ^ 48), c = getchar();
    return num * f;
}
#undef T
#define a QAQ
#define int long long
int as[100005], n, m, r, mod, dfn[100005], fa[100005], top[100005], hs[100005], sz[100005], dep[100005], a[100005];
#undef a

//
int addv[400005], sum[400005];
int Sn;
int GetLength(int t)
{
    int p = 1;
    while (p < t)p <<= 1ll;
    return p;
}
inline void pushdown()
{

}
inline void build(int n)
{
    Sn = GetLength(n);
    for (int i = 1; i <= n; i++)
    {
        addv[i + Sn - 1] = QAQ[i];
    }
    for (int i = Sn - 1; i; i--)sum[i] = (addv[i << 1] + addv[(i << 1) ^ 1]) % mod;
}
int res;
inline void query(int u, int l, int r, int L, int R, int adds)
{
    //printf("Searching... u = %d, [%d, %d], ad = %d\n", u, l, r, adds);
    if (L <= l&&r <= R){ res += sum[u] + ((addv[u] + adds) * (r - l + 1)); res %= mod; return; }
    else
    {
        int M = l + (r - l) / 2;
        if (L <= M)query(u << 1, l, M, L, R, (adds + addv[u]) % mod);
        if (R > M)query((u << 1) ^ 1, M + 1, r, L, R, (adds + addv[u]) % mod);
    }
}
#define min(a,b) (a>b?b:a)
#define max(a,b) (a<b?b:a)
inline void update(int u, int l, int r, int L, int R, int k){
    if (L <= l&&r <= R)
    {
        addv[u] += k;
        addv[u] %= mod;
    }
    else
    {
        int mid = l + (r - l) / 2;
        if (L <= mid)update(u<<1,l,mid, L, R, k);
        if (R>mid)update((u << 1) ^ 1, mid+1, r, L, R, k);
        sum[u] = (sum[u] + k*(1+min(r, R) - max(l, L))) % mod;
    }
}

struct Edge{
    int v, nxt;
}e[100005 << 1];
int h[100005], cnt = 1;
inline void addedge(int u, int v)
{
    e[cnt] = { v, h[u] };
    h[u] = cnt++;
}
int dfs1(int u, int fat, int dept)
{
    sz[u] = 1, fa[u] = fat, dep[u] = dept;
    int tmp = 0;
    for (int i = h[u]; i; i = e[i].nxt)
    {
        if (e[i].v == fat)continue;
        dfs1(e[i].v, u, dept + 1);
        sz[u] += sz[e[i].v];
        if (sz[e[i].v] > tmp)tmp = sz[e[i].v], hs[u] = e[i].v;
    }
    return 0;
}
int cn;
int dfs2(int u, int t)
{
    dfn[u] = ++cn;
    QAQ[cn] = as[u];
    top[u] = t;
    if (!hs[u])return 0;
    dfs2(hs[u], t);
    for (int i = h[u]; i; i = e[i].nxt)
    {
        if (e[i].v == fa[u] || e[i].v == hs[u])continue;
        dfs2(e[i].v, e[i].v);
    }
    return 0;
}
signed main()
{
    //freopen("C:\\Users\\Administrator\\Downloads\\P3384_2.in", "r", stdin);
    int n = read(), m = read(), r = read(); mod = read();
    for (int i = 1; i <= n; i++)as[i] = read()%mod;
    for (int i = 1; i < n; i++)
    {
        int x = read(), y = read();
        addedge(x, y); addedge(y, x);
    }
    dfs1(r, -1, 1);
    dfs2(r, r);
    build(n);

    while (m--)
    {
        int op = read();
        if (op == 2)
        {
            int x = read(), y = read();
            int ans = 0;
            while (top[x] != top[y])
            {
                if (dep[top[x]] < dep[top[y]])swap(x,y);
                res = 0;
                query(1, 1, Sn, dfn[top[x]], dfn[x], 0);
                ans = (ans+res)%mod;
                x = fa[x];
            }
            if (dep[x] > dep[y])swap(x, y);
            res = 0;
            query(1, 1, Sn, dfn[x], dfn[y], 0);
            printf("%d\n", (ans + res) % mod);
        }
        else if (op == 1)
        {
            int x = read(), y = read(), z = read();
            while (top[x] != top[y])
            {
                if (dep[top[x]] < dep[top[y]])swap(x, y);
                update(1, 1, Sn, dfn[top[x]], dfn[x], z);
                x = fa[x];
            }
            if (dep[x] > dep[y])swap(x, y);
            update(1,1,Sn,dfn[x], dfn[y], z);
        }
        else if (op == 3)
        {
            int x = read(), z = read();
            update(1,1,Sn,dfn[x], dfn[x] + sz[x] - 1, z);
        }
        else
        {
            int x = read();
            res = 0;
            query(1, 1, Sn, dfn[x], dfn[x] + sz[x] - 1, 0);
            printf("%d\n", res%mod);
        }
    }
    getchar();
    return 0;
}
2020/9/5 12:35
加载中...