头像

冰冷酒

沈阳化工大学




离线:1天前


最近来访(580)
用户头像
C.m
用户头像
x1uc
用户头像
宇宙有边
用户头像
Pein
用户头像
小洋567
用户头像
yxc的小迷妹
用户头像
kuchibi
用户头像
666--
用户头像
shallow的屑
用户头像
不好好学习请把我丢掉
用户头像
Z_zxn
用户头像
不再摆烂
用户头像
TREK
用户头像
云居
用户头像
玛卡巴卡要AC
用户头像
Z._4
用户头像
爱喝只因汤
用户头像
rzybz
用户头像
是光
用户头像
岸边的光熙


#include <bits/stdc++.h>

// #define int long long

using namespace std;

// #pragma GCC optimize(2, "Ofast", "inline")
// #pragma GCC optimize(3, "Ofast", "inline")

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

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

int T;

int n, m, a[N];
vector<int> G[N];

int depth[M], fa[N][21];
int q[N];

int block[N], first[N];
int nums[M], cnt;

int len;

struct node {
    int l, r, id, p;
}Query[N];

bool cmp(const node &a, const node &b) {
    if (block[a.l] != block[b.l]) return block[a.l] < block[b.l];
    return first[a.r] < first[b.r];
}

void dfs(int u, int father) {
    first[u] = ++ cnt;

    for (auto j : G[u]) {
        if (j == father) continue;
        depth[j] = depth[u] + 1;
        fa[j][0] = u;
        for (int k = 1; k <= 20; k ++)
            fa[j][k] = fa[fa[j][k - 1]][k - 1];
        dfs(j, u);
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 20; k >= 0; k -- )
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if (a == b) return a;
    for (int k = 20; k >= 0; k -- )
        if (fa[a][k] != fa[b][k])
            a = fa[a][k], b = fa[b][k];
    return fa[a][0];
}

int num_a[N], hs[N];
int len_a;

int ans[N];

int st[N];

void add_modui(int x) {
    st[a[x]] ^= 1;
    if (st[a[x]] % 2) {
        num_a[hs[a[x]]] ++;
    } else {
        num_a[hs[a[x]]] --;
    }
}

void move(int x, int y) {
    while (x != y) {
        if (depth[x] > depth[y]) swap(x, y);
        add_modui(y);
        y = fa[y][0];
    }
}

int query() {
    for (int i = 1; i <= len_a + 1; i ++) {
        if (num_a[i] != len_a) {
            for (int j = (i - 1) * len_a + 1; j < N; j ++) {
                if (st[j] % 2 == 0) {
                    return j;
                }
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    len_a = sqrt(N);
    for (int i = 1; i < N; i ++) hs[i] = (i - 1) / len_a + 1;

    cin >> T;
    while (T --) {
        cnt = 0;

        cin >> n >> m;

        for (int i = 1; i <= n; i ++) {
            cin >> a[i];
            G[i].clear();
            st[i] = num_a[i] = 0;
        }

        for (int i = 1; i < n; i ++) {
            int u, v;
            cin >> u >> v;
            G[u].push_back(v);
            G[v].push_back(u);
        }

        depth[0] = 0, depth[1] = 1;
        dfs(1, -1);

        len = sqrt(n);
        for (int i = 1; i <= n; i ++) {
            block[i] = (first[i] - 1) / len + 1;
        }

        for (int i = 1; i <= m; i ++) {
            int l, r;
            cin >> l >> r;
            if (block[l] > block[r]) swap(l, r);
            int p = lca(l, r);
            Query[i] = {l, r, i, p};
        }

        sort(Query + 1, Query + m + 1, cmp);

        int LCA = Query[1].p;
        move(Query[1].l, Query[1].r);
        add_modui(LCA);
        ans[Query[1].id] = query();
        add_modui(LCA);

        for (int i = 2; i <= m; i ++) {
            int id = Query[i].id, p = Query[i].p;
            move(Query[i - 1].l, Query[i].l);
            move(Query[i - 1].r, Query[i].r);
            add_modui(p);
            ans[id] = query();
            add_modui(p);
        }

        for (int i = 1; i <= m; i ++) {
            cout << ans[i] << '\n';
        }
    }

    return 0;
}



活动打卡代码 AcWing 16. 替换空格

冰冷酒
16天前
func replaceSpaces(str string) string {
    var sz = len(str)
    var res string = ""

    for i := 0; i < sz; i++ {
        if str[i] != ' ' {
            res += string(str[i])
        } else {
            res += "%20"
        }
    }
    return res
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 21. 斐波那契数列

冰冷酒
16天前
func Fibonacci(n int) int {
    if n == 0 {
        return 0
    } else if n == 1 || n == 2 {
        return 1
    } else {
        return Fibonacci(n - 1) + Fibonacci(n - 2)
    }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 804. n的阶乘

冰冷酒
16天前
package main

import "fmt"

var n, res int

func sum(x int) int {
    if x == 1 {
        return 1
    }
    return x * sum(x - 1)
}

func main() {
    fmt.Scan(&n)
    res = sum(n);
    fmt.Printf("%d", res)
}   

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 655. 天数转换

冰冷酒
17天前
package main

import "fmt"

func main() {
    var x int
    fmt.Scan(&x)

    fmt.Printf("%d ano(s)\n", x / 365)
    x %= 365

    fmt.Printf("%d mes(es)\n", x / 30)
    x %= 30

    fmt.Printf("%d dia(s)\n", x)
}   

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 654. 时间转换

冰冷酒
17天前
package main

import "fmt"

func main() {
    var x int
    fmt.Scan(&x)
    var hh, mm, ss int
    hh = x / 3600
    x %= 3600
    mm = x / 60
    x %= 60
    ss = x
    fmt.Printf("%d:%d:%d", hh, mm, ss)
}

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 653. 钞票

冰冷酒
17天前
package main

import "fmt"

func main() {
    var a = [10]int{100, 50, 20, 10, 5, 2, 1}
    var x int
    fmt.Scan(&x)
    fmt.Printf("%d\n", x)
    for i := 0; i <= 6; i ++ {
        var res int = x / a[i]
        x %= a[i]
        fmt.Printf("%d nota(s) de R$ %d,00\n", res, a[i])
    }
}

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 618. 燃料消耗

冰冷酒
19天前
package main

import "fmt"

func main() {
    var T, S float64
    fmt.Scan(&T, &S)
    fmt.Printf("%.3f\n", S * T / 12)
}

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 617. 距离

冰冷酒
19天前
package main

import "fmt"

func main() {
    var x int
    fmt.Scan(&x)
    fmt.Printf("%d minutos\n", x * 2)
}

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 616. 两点间的距离

冰冷酒
19天前
package main

import "fmt"
import "math"

func get_dist(x1, y1, x2, y2 float64) (float64) {
    dx:= x2 - x1
    dy:= y2 - y1
    res := math.Sqrt(dx * dx + dy * dy)
    return res
}

func main() {
    var x1, y1, x2, y2 float64
    fmt.Scanln(&x1, &y1)
    fmt.Scanln(&x2, &y2)

    fmt.Printf("%.4f", get_dist(x1, y1, x2, y2))
}

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~