#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n, i, m, st, qi, tot, l, r;
vector<pair<int, int> > adj[90005];
long long a, b, quer, we;
int p[90005];
int sub[90005];
int d[90005];
bool dontUse[90005];
pair<pair<int, int>, int> centroid;
bool cont;
pair<int, int> roots;
pair<int, int> dist;
pair<int, int> ans;
vector<int> marked;
vector<int> vert;
void dfs_ch(int x, int p=-1) {
sub[x] = 1;
for (auto y : adj[x]) {
if (y.X == p || dontUse[y.Y]) continue;
dfs_ch(y.X, x);
sub[x] += sub[y.X];
}
}
void find_centroid(int x, int p=-1) {
for (auto y : adj[x]) {
if (y.X == p || dontUse[y.Y]) continue;
if (sub[y.X] >= sub[x]/2) {
centroid = make_pair(make_pair(x, y.X), y.Y);
find_centroid(y.X, x);
}
}
}
void mark(int x, int p=-1) {
for (auto y : adj[x]) {
if (y.X == p || dontUse[y.Y]) continue;
marked.push_back(y.Y);
mark(y.X, x);
}
}
void find_dist(int x, int lookFor, int p=-1) {
for (auto y : adj[x]) {
if (y.X == p || dontUse[y.Y]) continue;
d[y.X] = d[x]+1;
if (d[y.X] == lookFor) {
marked.push_back(y.Y);
vert.push_back(y.X);
}
find_dist(y.X, lookFor, x);
}
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
m = (int)U.size();
n = N;
fill(dontUse, dontUse+n, false);
a = (long long)A;
b = (long long)B;
for (i=0; i < m; ++i) {
adj[U[i]].push_back(make_pair(V[i], i));
adj[V[i]].push_back(make_pair(U[i], i));
}
vector<int> w(m, 0);
we = ask(w);
tot = (int)(we/a);
cont = true;
st = 0;
do {
centroid = make_pair(make_pair(st, adj[st][0].X), adj[st][0].Y);
dfs_ch(st);
find_centroid(st);
dontUse[centroid.Y] = true;
vector<int> w(m, 0);
w[centroid.Y] = 1;
quer = ask(w);
if (quer > we) {
cont = false;
roots = centroid.X;
marked.clear();
mark(roots.X);
vector<int> w(m, 0);
for (auto v : marked) w[v] = 1;
quer = ask(w);
dist.X = (int)((quer-we)/(b-a));
dist.Y = tot-dist.X-1;
}
else {
marked.clear();
mark(centroid.X.X);
vector<int> w(m, 0);
for (auto v : marked) w[v] = 1;
quer = ask(w);
if (quer > we) st = centroid.X.X;
else st = centroid.X.Y;
}
} while (cont);
d[roots.X] = 0;
marked.clear();
vert.clear();
if (dist.X == 0) vert.push_back(roots.X);
else find_dist(roots.X, dist.X);
l = 0;
r = (int)marked.size()-1;
if (r == -1) answer(0, 1), return 0;
while (l < r) {
int mid = (l+r)/2;
vector<int> w(m, 0);
for (i=0; i <= mid; ++i) w[marked[i]] = 1;
quer = ask(w);
if (quer > we) r = mid;
else l = mid+1;
}
ans.X = vert[l];
d[roots.Y] = 0;
marked.clear();
vert.clear();
if (dist.Y == 0) vert.push_back(roots.Y);
else find_dist(roots.Y, dist.Y);
l = 0;
r = (int)marked.size()-1;
if (r == -1) answer(0, 1), return 0;
while (l < r) {
int mid = (l+r)/2;
vector<int> w(m, 0);
for (i=0; i <= mid; ++i) w[marked[i]] = 1;
quer = ask(w);
if (quer > we) r = mid;
else l = mid+1;
}
ans.Y = vert[l];
answer(ans.X, ans.Y);
}
/*
12 11 63 8242 2 11
0 1
1 2
1 3
3 4
4 5
0 6
6 7
7 8
8 9
8 10
7 11
*/
Compilation message
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:128:30: error: expected primary-expression before 'return'
128 | if (r == -1) answer(0, 1), return 0;
| ^~~~~~
highway.cpp:150:30: error: expected primary-expression before 'return'
150 | if (r == -1) answer(0, 1), return 0;
| ^~~~~~
