头像

呐呐呐呐

$\color{seagreen}{\mathcal{kkkk}}$




离线:59分钟前


最近来访(763)
用户头像
他太稳健了
用户头像
狼王穆图
用户头像
猫猫虫_2
用户头像
PrinceS
用户头像
我爱编程
用户头像
Resurgence1001
用户头像
Hxxj
用户头像
Scr丶
用户头像
用户头像
cubane
用户头像
V1
用户头像
栗子ing
用户头像
北海没有WA
用户头像
Mr.lonely_6
用户头像
Dawn._9
用户头像
Cold_heartless
用户头像
kimmmm
用户头像
acwing_68271
用户头像
2580000
用户头像
人活着就是为了时崎狂三


呐呐呐呐
23小时前
$A + B$

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void printf(int x) {System.out.println(x);}
    public static int scanf_int() {Scanner sc = new Scanner(System.in); return sc.nextInt();}
    public static String scanf_str() {Scanner sc = new Scanner(System.in); return sc.next();}
    public static String getline() {Scanner sc = new Scanner(System.in); return sc.nextLine();}
    // 快读
    public static String read()throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        return br.readLine();
    }
    // 快写
    public static void print(String str) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(str);
        bw.flush();
    }
    public static void main(String[] args) throws Exception {
        String[] str = getline().split(" ");
        int a = Integer.parseInt(str[0]), b = Integer.parseInt(str[1]);
        printf(a + b);
    }
}


import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();
        System.out.printf("DIFERENCA = %d\n", a * b - c * d);
    }
}

作者:我爱编程
链接:https://www.acwing.com/activity/content/code/content/3831489/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

两点之间的距离
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double x1 = sc.nextDouble(), y1 = sc.nextDouble();
        double x2 = sc.nextDouble(), y2 = sc.nextDouble();
        double dx = x1 - x2;
        double dy = y1 - y2;
        System.out.printf("%.4f\n", Math.sqrt(dx * dx + dy * dy));
    }
}

作者:我爱编程
链接:https://www.acwing.com/activity/content/code/content/3831489/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

钞票
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] money = {100,50,20,10,5,2,1};
        System.out.println(n);
        for (int x: money) {
            System.out.printf("%d nota(s) de R$ %d,00\n", n / x, x);
            n %= x;
        }
    }
}

作者:我爱编程
链接:https://www.acwing.com/activity/content/code/content/3831489/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


时间转换
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int hour = n / 3600;
        n %= 3600;
        int minute = n / 60;
        int second = n % 60;
        System.out.printf("%d:%d:%d\n", hour, minute,second);
    }
}

作者:我爱编程
链接:https://www.acwing.com/activity/content/code/content/3805135/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

倍数
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(), b = sc.nextInt();
        if (a % b == 0 || b % a == 0) System.out.println("Sao Multiplos");
        else System.out.println("Nao sao Multiplos");
    }
}


作者:我爱编程
链接:https://www.acwing.com/activity/content/code/content/3743974/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

区间
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(), b = sc.nextInt();
        if (a % b == 0 || b % a == 0) System.out.println("Sao Multiplos");
        else System.out.println("Nao sao Multiplos");
    }
}


作者:我爱编程
链接:https://www.acwing.com/activity/content/code/content/3743974/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

游戏时间
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(), b = sc.nextInt();
        if (a % b == 0 || b % a == 0) System.out.println("Sao Multiplos");
        else System.out.println("Nao sao Multiplos");
    }
}


作者:我爱编程
链接:https://www.acwing.com/activity/content/code/content/3743974/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。



#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long i64;

const int N = 1e5 + 10, M = 350;

int n, m, len;
int w[N];
i64 lzy[M], s[M];

int get(int i)
{
    return i / len;
}

void change(int l, int r, int d)
{
    if (get(l) == get(r))
        for ( ; l <= r; l ++ ) w[l] += d, s[get(r)] += d;
    else
    {
        int i = l, j = r;
        while (get(l) == get(i)) w[i] += d, s[get(i)] += d, i ++ ;
        while (get(r) == get(j)) w[j] += d, s[get(j)] += d, j -- ;
        for (int k = get(i); k <= get(j); k ++ ) lzy[k] += d, s[k] += len * d;
    }
}

i64 query(int l, int r)
{
    i64 res = 0;
    if (get(l) == get(r))
        for ( ; l <= r; l ++ ) res += w[l] + lzy[get(r)];
    else
    {
        int i = l, j = r;
        while (get(l) == get(i)) res += w[i] + lzy[get(i)], i ++ ;
        while (get(r) == get(j)) res += w[j] + lzy[get(j)], j -- ;
        for (int k = get(i); k <= get(j); k ++ ) res += s[k];
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);

    len = sqrt(n);

    for (int i = 1; i <= n; i ++ ) 
    {
        scanf("%d", &w[i]);
        s[get(i)] += w[i];
    }

    while (m -- )
    {
        char op[2]; 
        int l, r, d;
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'C')
        {
            scanf("%d", &d);
            change(l, r, d);
        }
        else printf("%lld\n", query(l, r));
    }

    return 0;
}



#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3e5 + 10, M = N * 2, K = 51, MOD = 998244353;

int n, m;
int s[N][K];
int h[N], e[M], ne[M], idx;
int dep[N], fa[N], sz[N];
int son[N], top[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int ksm(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = (1ll * res * a) % MOD;
        a = (1ll * a * a) % MOD;
        b >>= 1;
    }
    return res;
}

void dfs1(int u, int father)
{
    for (int k = 1; k <= 50; k ++ )
        s[u][k] = (s[father][k] + ksm(dep[u], k)) % MOD;

    sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        dep[j] = dep[u] + 1, fa[j] = u;
        dfs1(j, u);
        if (sz[son[u]] < sz[j]) son[u] = j;
        sz[u] += sz[j];
    }
}

void dfs2(int u, int tp)
{
    top[u] = tp;
    if (!son[u]) return ;
    dfs2(son[u], tp);
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    }
}

int lca(int u, int v)
{
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    return v;
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h);

    for (int i = 0; i < n - 1; i ++ ) 
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    dfs1(1, 0), dfs2(1, 1);

    scanf("%d", &m);

    while (m -- )
    {
        int u, v, k;
        scanf("%d%d%d", &u, &v, &k);
        int p = lca(u, v);
        printf("%d\n", ((s[u][k] + s[v][k] - s[p][k] - s[fa[p]][k]) % MOD + MOD) % MOD);
    }

    return 0;
}



#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = N * 2;

int n, m;
int h[N], e[M], ne[M], idx;
int dep[N], fa[N], sz[N];
int id[N], og[N], son[N], top[N], cnt;
struct Node
{
    int l, r;
    int v, lzy;
}tr[N << 2];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs1(int u)
{
    sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (dep[j]) continue;
        dep[j] = dep[u] + 1, fa[j] = u;
        dfs1(j);
        if (sz[son[u]] < sz[j]) son[u] = j;
        sz[u] += sz[j];
    }
}

void dfs2(int u, int tp)
{
    id[u] = ++ cnt, og[cnt] = u, top[u] = tp;
    if (!son[u]) return ;
    dfs2(son[u], tp);
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    }
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if (l == r) return ;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

void pushson(Node &u, int k)
{
    u.v += (u.r  - u.l + 1) * k;
    u.lzy += k;
}

void pushdown(int u)
{
    if (tr[u].lzy)
    {
        pushson(tr[u << 1], tr[u].lzy);
        pushson(tr[u << 1 | 1], tr[u].lzy);
        tr[u].lzy = 0;
    }
}

void pushup(int u)
{
    tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v;
}

void modify(int u, int l, int r, int k)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].v += (tr[u].r - tr[u].l + 1) * k;
        tr[u].lzy += k;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, k);
        if (r > mid) modify(u << 1 | 1, l, r, k);
        pushup(u);
    }
}

int query(int u, int x)
{
    if (tr[u].l == tr[u].r) return tr[u].v;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid) return query(u << 1, x);
    else return query(u << 1 | 1, x);
}

int query_path(int u)
{
    int w = query(1, id[u]), res;
    while (u)
    {
        int l = id[top[u]], r = id[u];
        while (l < r)
        {
            int mid = l + r >> 1;
            if (query(1, mid) >= w) r = mid;
            else l = mid + 1;
        }
        if (query(1, r) == w) res = og[r];
        u = fa[top[u]];
    }

    return res;
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    dep[1] = 1;
    dfs1(1), dfs2(1, 1);
    build(1, 1, n);

    while (m -- )
    {
        char op[2]; int k;
        scanf("%s%d", op, &k);
        if (*op == 'C') modify(1, id[k], id[k] + sz[k] - 1, 1);
        else printf("%d\n", query_path(k));
    }

    return 0;
}



#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = N * 2;

int n, m;
int h[N], w[N], e[M], ne[M], idx;
int dep[N], sz[N], fa[N];
int id[N], nw[N], son[N], top[N], cnt;
struct Node
{
    int l, r;
    int lc, rc;
    int s, laz;
}tr[N << 2];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs1(int u)
{
    sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (dep[j]) continue;
        dep[j] = dep[u] + 1, fa[j] = u;
        dfs1(j);
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j]) son[u] = j;
    }
}

void dfs2(int u, int tp)
{
    id[u] = ++ cnt, nw[cnt] = w[u], top[u] = tp;
    if (!son[u]) return ;
    dfs2(son[u], tp);

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    }
}

void pushup(Node &u, Node &l, Node &r)
{
    u.s = l.s + r.s;
    if (l.rc == r.lc) -- u.s;
    u.lc = l.lc, u.rc = r.rc;
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, nw[r], nw[r], 1, 0};
    if (l == r) return ;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void update_col(Node &u, int k)
{
    u.lc = u.rc = u.laz = k;
    u.s = 1;    
}

void pushdown(int u)
{
    auto &rt = tr[u], &lf = tr[u << 1], &rg = tr[u << 1 | 1];
    if (rt.laz)
    {
        update_col(lf, rt.laz);
        update_col(rg, rt.laz);
        rt.laz = 0;
    }
}

void update(int u, int l, int r, int k)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        update_col(tr[u], k);
        return ;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) update(u << 1, l, r, k);
    if (r > mid) update(u << 1 | 1, l, r, k);
    pushup(u);
}

Node query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (r <= mid) return query(u << 1, l, r);
    else if (l > mid) return query(u << 1 | 1, l, r);
    else 
    {
        Node res, left = query(u << 1, l, r), right = query(u << 1 | 1, l, r);
        pushup(res, left, right);
        return res;
    }
}

void update_path(int u, int v, int k)
{
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        update(1, id[top[u]], id[u], k);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    update(1, id[v], id[u], k);
}

int query_path(int u, int v)
{
    Node res, left = {0, 0, 0, 0, 0, 0}, right= {0, 0, 0, 0, 0, 0};
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v), swap(left, right);
        Node t = query(1, id[top[u]], id[u]);
        pushup(left, t, left);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v), swap(left, right);
    Node t = query(1, id[v], id[u]);
    pushup(left, t, left);
    swap(left.lc, left.rc);
    pushup(res, left, right);
    return res.s;
}

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ ) 
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    dep[1] = 1;
    dfs1(1), dfs2(1, 1);
    build(1, 1, n);

    while (m -- )
    {
        char op[2];
        int a, b, c;
        scanf("%s%d%d", op, &a, &b);
        if (*op == 'Q')
            printf("%d\n", query_path(a, b));
        else 
        {
            scanf("%d%d", &c);
            update_path(a, b, c);
        }
    }

    return 0;
}



#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long i64;

const int N = 3e5 + 10, M = N * 2;

int n, m;
int h[N], w[N], e[M], ne[M], idx;
int id[N], a[N], cnt;
int dep[N], sz[N], top[N], fa[N], son[N];
struct Node
{
    int l, r;
    i64 v, lazy;
}tr[N << 2];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs1(int u)
{
    sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (dep[j]) continue;
        fa[j] = u, dep[j] = dep[u] + 1;
        dfs1(j);
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j]) son[u] = j;
    }
}

void dfs2(int u, int tp)
{
    id[u] = ++ cnt, top[u] = tp;
    if (!son[u]) return ;
    dfs2(son[u], tp);

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    }
}

void pushup(int u)
{
    tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v;
}

void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];

    if (root.lazy)
    {
        left.lazy += root.lazy, left.v += (left.r - left.l + 1) * root.lazy;
        right.lazy += root.lazy, right.v += (right.r - right.l + 1) * root.lazy;
        root.lazy = 0;
    }
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, 0};
    if (l == r) return ;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void update(int u, int l, int r, int k)
{
    if (tr[u].l >= l && tr[u].r <= r) 
    {
        tr[u].lazy += k;
        tr[u].v += (tr[u].r - tr[u].l + 1) * k;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) update(u << 1, l, r, k);
        if (r > mid) update(u << 1 | 1, l, r, k);
        pushup(u);
    }
}

i64 query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;

    pushdown(u);
    i64 res = 0;
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) res = query(u << 1, l, r);
    if (r > mid) res += query(u << 1 | 1, l, r);
    return res;
}

void update_path(int u, int v, int k)
{
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        update(1, id[top[u]], id[u], k);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    update(1, id[v], id[u], k);
}

i64 query_path(int u, int v)
{
    i64 res = 0;
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        res += query(1, id[top[u]], id[u]);
        u = fa[top[u]];
    }

    if (dep[u] < dep[v]) swap(u, v);
    res += query(1, id[v], id[u]);

    return res;
}

void update_tree(int u, int k)
{
    update(1, id[u], id[u] + sz[u] - 1, k);
}

i64 query_tree(int u)
{
    return query(1, id[u], id[u] + sz[u] - 1);
}

int main()
{
    memset(h, -1, sizeof h);

    scanf("%d", &n);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    for (int i = 0; i < n - 1; i ++ ) 
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    dep[1] = 1;
    dfs1(1), dfs2(1, 1);
    build(1, 1, n);

    update(1, id[a[1]], id[a[1]], 1);
    for (int i = 2; i <= n; i ++ )
    {
        update(1, id[a[i - 1]], id[a[i - 1]], -1);
        update_path(a[i - 1], a[i], 1);
    }
    update(1, id[a[n]], id[a[n]], -1);

    for (int i = 1; i <= n; i ++ ) 
        printf("%d\n", query(1, id[i], id[i]));

    return 0;
}



#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = N * 2;

int n, m;
int c[N], w[N];
int h[N], e[M], ne[M], idx;
int dep[N], fa[N], son[N];
int id[N], sz[N], top[N], cnt;
struct Node
{
    int l, r;
    int s, v;
}tr[N * 30];
int root[N], _idx;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs1(int u)
{
    sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (dep[j]) continue;
        dep[j] = dep[u] + 1, fa[j] = u;
        dfs1(j);
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j]) son[u] = j;
    }
}

void dfs2(int u, int tp)
{
    id[u] = ++ cnt, top[u] = tp;

    if (!son[u]) return ;
    dfs2(son[u], tp);

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    }
}

void modify(int &u, int l, int r, int x, int k)
{
    if (!u) u = ++ _idx;
    if (l == r) 
    {
        tr[u].s = tr[u].v = k;
        return ;
    }
    int mid = l + r >> 1;
    if (x <= mid) modify(tr[u].l, l, mid, x, k);
    else modify(tr[u].r, mid + 1, r, x, k);
    tr[u].s = tr[tr[u].l].s + tr[tr[u].r].s;
    tr[u].v = max(tr[tr[u].l].v, tr[tr[u].r].v);
}

int query(int u, int l, int r, int ls, int rs, int type)
{
    if (l >= ls && r <= rs) return type ? tr[u].s : tr[u].v;
    int mid = l + r >> 1;
    int left = 0, right = 0;
    if (ls <= mid) left = query(tr[u].l, l, mid, ls, rs, type);
    if (rs > mid) right = query(tr[u].r, mid + 1, r, ls, rs, type);
    return type ? (left + right) : max(left, right); 
}

int query_path(int u, int v, int c, int type)
{
    int res = 0;
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        int v = query(root[c], 1, N - 1, id[top[u]], id[u], type);
        res = type ? res + v : max(res, v);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    v = query(root[c], 1, N - 1, id[v], id[u], type);
    res = type ? res + v : max(res, v);

    return res;
}

int main()
{
    memset(h, -1, sizeof h);

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i ++ ) scanf("%d%d", &w[i], &c[i]);

    for (int i = 0; i < n - 1; i ++ ) 
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    dep[1] = 1;
    dfs1(1), dfs2(1, 1);

    for (int i = 1; i <= n; i ++ ) 
        modify(root[c[i]], 1, N - 1, id[i], w[i]);

    while (m -- )
    {
        char op[2]; int x, y;
        cin >> op >> x >> y;
        if (op[1] == 'C')
        {
            modify(root[y], 1, N - 1, id[x], w[x]);
            modify(root[c[x]], 1, N - 1, id[x], 0);
            c[x] = y;
        }
        else if (op[1] == 'W')
        {
            modify(root[c[x]], 1, N - 1, id[x], y);
            w[x] = y;
        }
        else if (op[1] == 'S') printf("%d\n", query_path(x, y, c[x], 1));
        else printf("%d\n", query_path(x, y, c[x], 0));
    }

    return 0;
}



照着抄都抄出bug,还调了好久

#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

const int N = 40010, M = N * 2;

int n, m, q, K;
int h[N], e[M], ne[M], idx;
int dep[N], fa[N], sz[N];
int id[N], og[N], son[N], top[N], cnt;
int f[N], p[N];
struct Node
{
    int l, r;
    vector<int> v;
}tr[N << 2];
multiset<int, greater<int>> S[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs1(int u)
{
    sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (dep[j]) continue;
        fa[j] = u, dep[j] = dep[u] + 1;
        dfs1(j);
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j]) son[u] = j;
    }
}

void dfs2(int u, int tp)
{
    id[u] = ++ cnt;
    og[cnt] = u, top[u] = tp;

    if (!son[u]) return ;
    dfs2(son[u], tp);

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    }
}

void update(int u, int r)
{
    int k = 0;
    tr[u].v = vector<int>(K);
    for (auto it = S[r].begin(); it != S[r].end() && k < K; it ++ , k ++ )
        tr[u].v[k] = *it;
}

void pushup(vector<int>& u, vector<int>& left, vector<int>& right)
{
    int i = 0, j = 0, k = 0;
    while (i < K && j < K && k < K)
        if (left[i] > right[j]) u[k ++ ] = left[i ++ ];
        else u[k ++ ] = right[j ++ ];
}

void pushup(int u)
{
    pushup(tr[u].v, tr[u << 1].v, tr[u << 1 | 1].v);
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    tr[u].v = vector<int>(K);
    if (l == r)
    {
        update(u, og[r]);
        return ;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int x, int k, int t)
{
    if (tr[u].l == tr[u].r)
    {
        if (!t) S[og[x]].erase(S[og[x]].find(k));
        else S[og[x]].insert(k);
        update(u, og[x]);
        return ;
    }

    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid) modify(u << 1, x, k, t);
    else modify(u << 1 | 1, x, k, t);
    pushup(u);
}

vector<int> query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;
    int mid = tr[u].l + tr[u].r >> 1;
    if (r <= mid) return query(u << 1, l, r);
    else if (l > mid) return query(u << 1 | 1, l, r);
    else
    {
        vector<int> res(K);
        auto left = query(u << 1, l, r), right = query(u << 1 | 1, l, r);
        pushup(res, left, right);
        return res;
    }
}

vector<int> query_path(int u, int v)
{
    vector<int> res(K), t, ts;

    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        t = res, ts = query(1, id[top[u]], id[u]);
        pushup(res, t, ts);
        u = fa[top[u]];
    }

    if (dep[u] < dep[v]) swap(u, v);
    t = res, ts = query(1, id[v], id[u]);
    pushup(res, t, ts);
    return res;
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h);

    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    scanf("%d", &m);

    for (int i = 1; i <= m; i ++ )
    {
        scanf("%d%d", &f[i], &p[i]);
        S[p[i]].insert(f[i]);
    }

    scanf("%d%d", &q, &K);

    dep[1] = 1;
    dfs1(1), dfs2(1, 1);
    build(1, 1, n);

    while (q -- )
    {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);

        if (t == 1)
        {
            auto res = query_path(x, y);
            if (res[0] == 0) printf("%d", -1);
            else
                for (int i = 0; i < res.size() && res[i]; i ++ )
                    printf("%d ", res[i]);
            puts("");        
        }
        else if (t == 2)
        {
            modify(1, id[p[x]], f[x], 0);
            modify(1, id[y], f[x], 1);
            p[x] = y;
        }
        else
        {
            modify(1, id[p[x]], f[x], 0);
            modify(1, id[p[x]], y, 1);
            f[x] = y;
        }
    }

    return 0;
}



靠!这题数据真的坑!!!!!!!!!!!!所有变成全部变成long 才行!

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define int long long

typedef long long i64;

const int N = 1e5 + 10, M = N * 2;

int n, m;
int h[N], w[N], e[M], ne[M], idx;
int dep[N], fa[N], sz[N];
int id[N], nw[N], son[N], top[N], cnt;
struct Node
{
    int l, r;
    i64 v, lazy;
}tr[N << 2];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs1(int u)
{
    sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (dep[j]) continue;
        dep[j] = dep[u] + 1, fa[j] = u;
        dfs1(j);
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j]) son[u] = j;
    }
}

void dfs2(int u, int tp)
{
    id[u] = ++ cnt, nw[cnt] = w[u], top[u] = tp;

    if (!son[u]) return ;
    dfs2(son[u], tp);

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    }
}

void pushup(int u)
{
    tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v;
}

void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];

    if (root.lazy)
    {
        left.lazy += root.lazy, left.v += (1ll * left.r - left.l + 1) * root.lazy;
        right.lazy += root.lazy, right.v += (1ll * right.r - right.l + 1) * root.lazy;
        root.lazy = 0;
    }
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, nw[r], 0};
    if (l == r) return ;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void update(int u, int l, int r, int k)
{
    if (tr[u].l >= l && tr[u].r <= r) 
    {
        tr[u].lazy += k;
        tr[u].v += (tr[u].r - tr[u].l + 1) * k;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) update(u << 1, l, r, k);
        if (r > mid) update(u << 1 | 1, l, r, k);
        pushup(u);
    }
}

i64 query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;

    pushdown(u);
    i64 res = 0;
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) res = query(u << 1, l, r);
    if (r > mid) res += query(u << 1 | 1, l, r);
    return res;
}

i64 query_path(int u, int v)
{
    i64 res = 0;
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        res += query(1, id[top[u]], id[u]);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    res += query(1, id[v], id[u]);

    return res;
}

signed main()
{
    memset(h, -1, sizeof h);

    scanf("%lld%lld", &n, &m);

    for (int i = 1; i <= n; i ++ ) scanf("%lld", &w[i]);

    for (int i = 0; i < n - 1; i ++ ) 
    {
        int a, b;
        scanf("%lld%lld", &a, &b);
        add(a, b), add(b, a);
    }

    dep[1] = 1;
    dfs1(1), dfs2(1, 1);
    build(1, 1, n);

    while (m -- )
    {
        int t, x, k;
        scanf("%lld%lld", &t, &x);

        if (t == 1)
        {
            scanf("%lld", &k);
            update(1, id[x], id[x], k);
        }
        else if (t == 2)
        {
            scanf("%lld", &k);
            update(1, id[x], id[x] + sz[x] - 1, k);
        }
        else printf("%lld\n", query_path(1, x));
    }

    return 0;
}


分享 树链剖分

树链剖分

  • ① 将一颗树转化成一个序列
  • ② 将树中的每一条路径转化成 $log_n$ 段连续区间

重儿子:对于某个节点而言,节点个数最多的子节点

  • 重边:重儿子和其父节点之间的边。
  • 重链:由极大的重边构成的路径。

轻儿子:该节点的重儿子以外的节点

  • 轻边:轻儿子和其父节点之间的边

每一个点都要在一个重链里

  • 重儿子在他父节点的重链里
  • 轻儿子在以这个点开头的以下的重链里面
  • 叶节点是轻儿子,那么这就是一个单独(特殊)的重链
  • 所以所有轻儿子都是一条链的顶点

$dfs$ 的时候按优先遍历重儿子的顺序 创建 $dfs$ 序

  • 这样可以让一条重链的编号是连续的
核心结论:树中任意一条路径都可以拆分成 $log_n$ 条重链,每条重链的编号都是连续的,即可拆分成 $log_n$ 个连续区间

如何将一条路径转转化成若干条重链?

  • 从两个点最底下的链不断往上爬,每次用比较低的点爬
2568.树链剖分
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long i64;

const int N = 1e5 + 10, M = N * 2;

int n, m;
int h[N], w[N], e[M], ne[M], idx;
int id[N], nw[N], cnt;
int dep[N], sz[N], top[N], fa[N], son[N];
struct Node
{
    int l, r;
    i64 v, lazy;
}tr[N << 2];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs1(int u)
{
    sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (dep[j]) continue;
        fa[j] = u, dep[j] = dep[u] + 1;
        dfs1(j);
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j]) son[u] = j;
    }
}

void dfs2(int u, int tp)
{
    id[u] = ++ cnt, nw[cnt] = w[u], top[u] = tp;
    if (!son[u]) return ;
    dfs2(son[u], tp);

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2(j, j);
    }
}

void pushup(int u)
{
    tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v;
}

void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];

    if (root.lazy)
    {
        left.lazy += root.lazy, left.v += (left.r - left.l + 1) * root.lazy;
        right.lazy += root.lazy, right.v += (right.r - right.l + 1) * root.lazy;
        root.lazy = 0;
    }
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, nw[r], 0};
    if (l == r) return ;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void update(int u, int l, int r, int k)
{
    if (tr[u].l >= l && tr[u].r <= r) 
    {
        tr[u].lazy += k;
        tr[u].v += (tr[u].r - tr[u].l + 1) * k;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) update(u << 1, l, r, k);
        if (r > mid) update(u << 1 | 1, l, r, k);
        pushup(u);
    }
}

i64 query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;

    pushdown(u);
    i64 res = 0;
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) res = query(u << 1, l, r);
    if (r > mid) res += query(u << 1 | 1, l, r);
    return res;
}

void update_path(int u, int v, int k)
{
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        update(1, id[top[u]], id[u], k);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    update(1, id[v], id[u], k);
}

i64 query_path(int u, int v)
{
    i64 res = 0;
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        res += query(1, id[top[u]], id[u]);
        u = fa[top[u]];
    }

    if (dep[u] < dep[v]) swap(u, v);
    res += query(1, id[v], id[u]);

    return res;
}

void update_tree(int u, int k)
{
    update(1, id[u], id[u] + sz[u] - 1, k);
}

i64 query_tree(int u)
{
    return query(1, id[u], id[u] + sz[u] - 1);
}

int main()
{
    memset(h, -1, sizeof h);

    scanf("%d", &n);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    for (int i = 0; i < n - 1; i ++ ) 
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    dep[1] = 1;
    dfs1(1), dfs2(1, 1);
    build(1, 1, n);

    scanf("%d", &m);

    while (m -- )
    {
        int t, u, v, k;
        scanf("%d%d", &t, &u);

        if (t == 1) 
        {
            scanf("%d%d", &v, &k);
            update_path(u, v, k);
        }
        else if (t == 2)
        {
            scanf("%d", &k);
            update_tree(u, k);
        }
        else if (t == 3)
        {
            scanf("%d", &v);
            printf("%lld\n", query_path(u, v));
        }
        else printf("%lld\n", query_tree(u));
    }

    return 0;
}