#include <bits/stdc++.h>
#include "Aoi.h"
using namespace std;
using ll = long long;
const ll inf = 1e17;
#define int ll
#define fr first
#define sc second
string toString(int n, int nr) {
string ans;
for (int i = 0; i < n; i ++) {
ans.push_back('0' + nr % 2);
nr /= 2;
}
return ans;
}
string aoi(signed n, signed m, signed q, signed k, vector<signed> a, vector<signed> b, vector<long long> c, vector<signed> t, vector<signed> x) {
vector<vector<int>> vec(n);
for (int i = 0; i < m; i ++) {
vec[a[i]].push_back(i);
vec[b[i]].push_back(i);
}
vector<bool> viz(n, false);
vector<ll> dist(n, inf);
vector<int> papa(n);
vector<vector<int>> sons(n);
priority_queue<pair<ll, int>> pq;
pq.push({0, 0});
dist[0] = 0;
while (!pq.empty()) {
auto y = pq.top();
pq.pop();
if (viz[y.sc])
continue;
viz[y.sc] = true;
for (auto i : vec[y.sc]) {
int j = (a[i] == y.sc ? b[i] : a[i]);
if (dist[j] > dist[y.sc] + c[i]) {
dist[j] = dist[y.sc] + c[i];
papa[j] = i;
pq.push({-dist[j], j});
}
}
}
vector<int> contrib(n);
for (auto i : t) {
contrib[i] ++;
while (i != 0) {
i = (a[papa[i]] == i ? b[papa[i]] : a[papa[i]]);
contrib[i] ++;
}
}
for (int i = 1; i < n; i ++)
sons[(a[papa[i]] == i ? b[papa[i]] : a[papa[i]])].push_back(i);
vector<bool> inTree(n);
for (int i = 0; i < n; i ++) {
int mx = 0;
for (auto j : sons[i])
mx = max(mx, contrib[(a[j] == i ? b[j] : a[j])]);
if (mx != contrib[i])
inTree[i] = true;
}
vector<int> papaTree(n);
vector<vector<int>> fiiTree(n);
int root = 0;
for (int i = 0; i < n; i ++) {
if (!inTree[i])
continue;
int nod = i;
while ((nod == i || !inTree[nod]) && nod != 0)
nod = (a[papa[nod]] == nod ? b[papa[nod]] : a[papa[nod]]);
if (i == 0 || (nod == 0 && i != 0 && !inTree[0])) {
root = i;
papaTree[i] = -1;
} else {
papaTree[i] = nod;
fiiTree[papaTree[i]].push_back(i);
}
}
string ans;
int nr = 0;
vector<int> ass(n);
for (int i = 0; i < n; i ++)
if (inTree[i])
ass[i] = nr ++;
for (int i = 0; i < n; i ++)
if (inTree[i]) {
if (i == root) {
ans += toString(5, ass[i]);
} else {
ans += toString(5, ass[papaTree[i]]);
}
}
for (int i = 0; i < q; i ++)
ans += toString(5, ass[t[i]]);
vector<int> lipsa(m, -1), raspuns(k, 31);
for (int i = 0; i < k; i ++)
lipsa[x[i]] = i;
for (int i = 0; i < n; i ++) {
if (!inTree[i])
continue;
int nod = i;
while ((nod == i || !inTree[nod]) && nod != 0) {
if (lipsa[papa[nod]] != -1)
raspuns[lipsa[papa[nod]]] = ass[i];
nod = (a[papa[nod]] == nod ? b[papa[nod]] : a[papa[nod]]);
}
}
for (int i = 0; i < k; i ++)
ans += toString(5, raspuns[i]);
return ans;
}
#include <bits/stdc++.h>
#include "Bitaro.h"
using namespace std;
using ll = long long;
const ll inf = 1e17;
#define fr first
#define sc second
#define int ll
int toInt(int n, string s) {
int nr = 0;
for (int i = n - 1; i >= 0; i --) {
nr *= 2;
nr += s[i] - '0';
}
return nr;
}
int inter(int l, int r, string &t) {
string s;
for (int i = l; i < r; i ++)
s += t[i];
return toInt(r - l, s);
}
void bitaro(signed n, signed m, signed q, signed k, vector<signed> a, vector<signed> b, vector<ll> c, vector<signed> t, vector<signed> x, string s) {
int noduri = (s.size() - 5 * k - 5 * q) / 5;
vector<vector<int>> uses(noduri);
for (int i = 0; i < k; i ++) {
int g = inter(5 * i + 5 * (q + noduri), 5 * (i + 1) + 5 * (q + noduri), s);
if (g == 31)
continue;
uses[g].push_back(x[i]);
}
vector<bool> cooked(m, false);
for (auto i : x) {
cooked[i] = true;
c[i] = 0;
}
for (int qs = 0; qs < q; qs ++) {
int leaf = inter(5 * (qs + noduri), 5 * (qs + noduri + 1), s);
vector<vector<int>> vec(n);
for (int i = 0; i < m; i ++) {
if (!cooked[i]) {
vec[a[i]].push_back(i);
vec[b[i]].push_back(i);
}
}
auto baga = uses[leaf];
int j = leaf;
while (inter(5 * j, 5 * (j + 1), s) != j) {
j = inter(5 * j, 5 * (j + 1), s);
for (auto l : uses[j])
baga.push_back(l);
}
for (auto i : baga) {
vec[a[i]].push_back(i);
vec[b[i]].push_back(i);
}
vector<bool> viz(n, false);
vector<ll> dist(n, inf);
vector<int> papa(n);
vector<vector<int>> sons(n);
priority_queue<pair<ll, int>> pq;
pq.push({0, 0});
dist[0] = 0;
while (!pq.empty()) {
auto y = pq.top();
pq.pop();
if (viz[y.sc])
continue;
viz[y.sc] = true;
for (auto i : vec[y.sc]) {
int l = (a[i] == y.sc ? b[i] : a[i]);
if (dist[l] > dist[y.sc] + c[i]) {
dist[l] = dist[y.sc] + c[i];
papa[l] = i;
pq.push({-dist[l], l});
}
}
}
vector<signed> ans;
int nod = t[qs];
while (nod != 0) {
ans.push_back(papa[nod]);
nod = (a[papa[nod]] == nod ? b[papa[nod]] : a[papa[nod]]);
}
reverse(ans.begin(), ans.end());
answer(ans);
}
}
