// moreflags=grader.cpp
// :( (why did I implement the centroid before trying to figure out an easier solution...
// and that's just for the tree subtask.)
#include "highway.h"
#include<cassert>
#include<vector>
#include<cstdint>
#include<algorithm>
struct Solve{
struct Edge{
int node, index;
};
std::vector<std::vector<Edge>> add;
int64_t A, B;
int distance;
std::vector<int> query; // some common query vector
/*
int curSize;
int subsize(int node, int par){
int result=1;
for(auto [child,_]: add[node]) if(child!=par) result+=subsize(child, node);
return result;
}
int throwCentroid(int node, int par){
int result=1, maxChild=0;
for(auto [child,_]: add[node]) if(child!=par){
auto const childSize=throwCentroid(child, node);
maxChild=std::max(maxChild, childSize);
result+=childSize;
}
if(std::max(maxChild, curSize-result)*2<=curSize) throw node;
return result;
}
int centroid(int node){
curSize=subsize(node, -1);
try{
throwCentroid(node, -1);
}catch(int centroid){return centroid;}
assert(false); __builtin_unreachable();
}
void work(int node){
if(add[node].size()==1 and add[add[node][0]].size()==1){
answer(node, add[node][0]);
return;
}
node=centroid(node);
std::vector<std::pair<int, Edge>> branches(add[node].size());
std::transform(begin(add[node]), end(add[node]), branches.begin(),[&](auto edge){
return std::pair(subsize(edge.node, node), edge);
});
std::sort(begin(branches), end(branches),[&](auto first, auto sec){return first.first<sec.first;});
int split=0;
{ // find a balanced split
int left=0, right=curSize;
while(split<(int)branches.size()){
if(std::abs((left+branches[split].first)-(right-branches[split].first))<std::abs(left-right)){
left+=branches[split].first;
right-=branches[split].first;
++split;
}
}
}
auto const toll=[&]{
query.assign(add.size()-1, 0);
for(int i=0; i<split; ++i){
query[branches[i].second.index]=1;
fillQuery(branches[i].second.node, node);
}
return ask(std::move(query);
}();
assert(A*distance<=toll); assert(toll<=B*distance);
if(A*distance==toll){
}else if(B*distance==toll){
}else{
}
}
*/
void fillQuery(int node, int par){
// fill all in subtree of node, not fill node..par
for(auto [child, edgeIndex]: add[node]) if(child!=par){
assert(query[edgeIndex]==0);
query[edgeIndex]=1;
fillQuery(child, node);
}
}
std::vector<Edge> layer; // some nodes on the same layer, edgeIndex is the index of edge to parent
void makeList(int node, int parent, int distance){
for(auto [child, index]: add[node]) if(child!=parent){
if(distance==1)
layer.push_back({child, index});
else
makeList(child, node, distance-1);
}
}
int solve1(int node, int parent, int distanceNode){
assert(distanceNode>=0);
if(distanceNode==0) return node;
layer.clear();
makeList(node, parent, distanceNode);
int left=0;
{
int right=(int)layer.size();
while(right-left>1){
auto const mid=(left+right)>>1;
query.assign(add.size()-1, 0);
std::for_each(layer.begin()+left, layer.begin()+mid, [&](auto it){
query[it.index]=1;
});
if(ask(std::move(query))>A*distance) right=mid; // [left..mid] contains the target
else left=mid;
}
}
return layer[left].node;
}
//std::pair<int, int> solve(){
void solve(){
assert(A<B);
distance=int(ask(std::vector<int>(add.size()-1, 0))/A);
//work(0);
int left=0;
{
int right=(int)add.size()-1;
while(right-left>1){
auto const mid=(left+right)>>1;
query.assign(add.size()-1, 0);
std::fill(query.begin()+left, query.begin()+mid, 1);
if(ask(std::move(query))>A*distance) right=mid;
else left=mid;
}
}
// now left is an edge on the S..T path
int node, other;
for(node=0;; ++node){
for(auto [other_, edgeIndex]: add[node]) if(edgeIndex==left) {
other=other_;
goto break_outer;
}
}
break_outer:
query.assign(add.size()-1, 0);
fillQuery(node, other);
auto const toll1=ask(std::move(query));
auto const delta=toll1-A*distance;
assert(delta%(B-A)==0);
auto const distanceNode=int(delta/(B-A));
auto const s=solve1(node, other, distanceNode);
auto const t=solve1(other, node, distance-distanceNode-1);
answer(s, t);
// does "unspecified order" include "in parallel"?...
}
};
void find_pair(int numNode, std::vector<int> U, std::vector<int> V, int A, int B) {
int const numEdge = (int)U.size();
if(numEdge!=numNode-1) return;
Solve solve{{}, A, B};
solve.add.resize(numNode);
for(int index=0; index<numEdge; ++index){
solve.add[U[index]].push_back({V[index], index});
solve.add[V[index]].push_back({U[index], index});
}
/*
auto const [s, t]=solve.solve();
answer(s, t);
*/
solve.solve();
}
