#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, nnn;
vector<pair<int, int> > adj[90005];
long long a, b, quer, we;
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];
}
nnn = sub[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] >= nnn/2) {
centroid = make_pair(make_pair(x, y.X), y.Y);
find_centroid(y.X, x);
break;
}
}
}
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);
}
else 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+m, 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 = rand()%n;
l = 0;
r = m-1;
while (l < r) {
int mid = (l+r)/2;
vector<int> w(m, 0);
for (i=0; i <= mid; ++i) w[i] = 1;
quer = ask(w);
if (quer > we) r = mid;
else l = mid+1;
}
roots.X = U[l];
roots.Y = V[l];
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;
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;
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;
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:101:15: error: redeclaration of 'std::vector<int> w'
101 | vector<int> w(m, 0);
| ^
highway.cpp:78:15: note: 'std::vector<int> w' previously declared here
78 | vector<int> w(m, 0);
| ^
