1.1万

TREK
kuchibi

C.m
x1uc

Pein

yxc的小迷妹
666--
shallow的屑

Z_zxn

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;
}



22天前
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
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


22天前
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)
}
}
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~


22天前
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)
}

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


22天前
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)
}

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


23天前
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)
}

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


23天前
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])
}
}

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


24天前
package main

import "fmt"

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

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


24天前
package main

import "fmt"

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

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


24天前
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))
}

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