1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
| #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e5 + 5;
const int SN = 2e6 + 5;
const int M = 1e5;
const int L = 18;
const LL M1 = 1000000181ll, A1 = 1145141ll;
const LL M2 = 998244353ll, A2 = 1145141ll;
LL f1[N], f2[N];
void init(){
f1[0] = f1[1] = f2[0] = f2[1] = 1ll;
for(int i = 2; i <= M; i++) f1[i] = f1[i - 1] * A1 % M1, f2[i] = f2[i - 1] * A2 % M2;
}
int upd1(LL x){return x >= M1 ? x - M1 : x;}
int upd2(LL x){return x >= M2 ? x - M2 : x;}
PII operator + (PII x, PII y){return {upd1(x.first + y.first), upd2(x.second + y. second)};}
PII operator - (PII x, PII y){return {upd1(x.first - y.first + M1), upd2(x.second - y. second + M2)};}
PII operator * (PII x, int y){return {x.first * (M1 + y) % M1, x.second * (M2 + y) % M2};}
PII operator * (int x, PII y){return y * x;}
struct node{
int lc, rc;
PII val;
}tr[SN]; int cnt, rt[N];
int n, q;
int col[N];
void link(int &x, int l, int r, int p){
tr[++cnt] = tr[x];
x = cnt;
tr[x].val = tr[x].val + PII{f1[p], f2[p]};
if(l == r) return ;
int mid = (l + r) / 2;
if(p <= mid) link(tr[x].lc, l, mid, p);
else link(tr[x].rc, mid + 1, r, p);
}
PII calc(const vector<PII> &x){
PII ans = {0, 0};
for(auto [p, type] : x){
ans = ans + tr[p].val * type;
}
return ans;
}
vector<PII> gleft(vector<PII> x){
for(auto& [p, type] : x) p = tr[p].lc;
return x;
}
vector<PII> gright(vector<PII> x){
for(auto& [p, type] : x) p = tr[p].rc;
return x;
}
int findans(int l, int r, int limit, vector<PII> x){
if(limit > r || calc(x) == PII{0, 0}) return -1;
if(l == r) return l;
int mid = (l + r) >> 1;
int ans = -1;
if(limit <= mid) ans = findans(l, mid, limit, gleft(x));
if(ans == -1) ans = findans(mid + 1, r, limit, gright(x));
return ans;
}
struct Edge{
int y, next;
}a[N * 2]; int len, las[N];
int fa[N][L], dep[N];
void ins(int x, int y){a[++len] = {y, las[x]}; las[x] = len;}
void dfs(int x){
for(int i = 1; i < L; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1];
link(rt[x], 1, M, col[x]);
for(int k = las[x]; k; k = a[k].next){
int y = a[k].y;
if(y == fa[x][0]) continue;
rt[y] = rt[x];
fa[y][0] = x;
dep[y] = dep[x] + 1;
dfs(y);
}
}
vector<int> v;
int findlca(int x, int y){
if(dep[x] < dep[y]) swap(x, y);
for(int i = L - 1; i >= 0; i--){
if(dep[x] - dep[y] >= (1 << i)) x = fa[x][i];
}
if(x == y) return x;
for(int i = L - 1; i >= 0; i--){
if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
}
return fa[x][0];
}
int main(){
cin.sync_with_stdio(false);
init();
cin >> n;
for(int i = 1; i <= n; i++) cin >> col[i];
for(int i = 2; i <= n; i++){
int x, y;
cin >> x >> y;
ins(x, y);
ins(y, x);
}
dep[1] = 1; dfs(1);
cin >> q;
for(int i = 1; i <= q; i++){
int x1, y1, x2, y2, cnt;
cin >> x1 >> y1 >> x2 >> y2 >> cnt;
vector<int> ans;
vector<PII> t;
t.resize(8);
int lca = findlca(x1, y1);
t[0]={rt[x1], 1};
t[1]={rt[y1], 1};
t[2]={rt[lca], -1};
t[3]={rt[fa[lca][0]], -1};
lca = findlca(x2, y2);
t[4]={rt[x2], -1};
t[5]={rt[y2], -1};
t[6]={rt[lca], 1};
t[7]={rt[fa[lca][0]], 1};
int pre = 0;
for(int j = 1; j <= cnt; j++){
pre = findans(1, M, pre + 1, t);
if(pre == -1) break;
ans.push_back(pre);
}
cout << ans.size();
for(auto x : ans) cout << " " << x;
cout << "\n";
}
return 0;
}
|
