题意：交互题，给定一个简单无向图和$A,B(1\leq A\lt B)$，你可以对每条边指定其边权为$A$或$B$后通过交互库询问$S\rightarrow T$的最短路（$S,T$在程序运行之前已经确定），但你不知道$S,T$，现在要求$S$和$T$
无论是什么做法，我们首先需要知道边权为$1$时的最短路$dis$，在开始时把所有边设为$A$，调用一次即可
从部分分入手，第一个部分分（subtask1,2）：图是一棵树，已知根是$S$，求$T$
因为只能调用很少次交互库，所以考虑二分
我们在bfs序上二分，假设当前二分到$[l,r]$，我们要检查$T$的bfs序是否在$[l,mid]$中，如果我们将bfs序在$[1,mid]$中的点的祖先边全部设为$A$，将其他边设为$B$，并且此时最短路为$dis\cdot A$，那么显然$T$的bfs序在$[l,mid]$中（因为任何bfs序在$[mid+1,r]$中的节点到根至少经过一条$B$边），于是时间复杂度为$O(n\log n)$，调用次数为$1+\left\lceil\log_2n\right\rceil$
然后是第二个部分分（subtask3,4）：图是一棵树
如果我们能找出一条在$S\rightarrow T$最短路上的边，那么删掉这条边后对两棵树套用上面的算法即可
要找到任意一条这样的边，还是得二分，二分边的编号，二分到$[l,r]$时把$[1,mid]$的边设为$B$，把$[mid+1,n-1]$的边设为$A$，如果最短路没有变化，那么这条边在$[mid+1,r]$，否则在$[l,mid]$，于是时间复杂度为$O(n\log_2n)$，调用次数为$1+\left\lceil\log_2n\right\rceil+2\left\lceil\log_2\frac n2\right\rceil$
然后是一般情况（subtask5,6）
我们同样想找到一条在$S\rightarrow T$的任意一条最短路上的边，还是得二分边的编号，一开始把所有边设为$A$，二分到$[l,r]$时先把$[l,mid]$设为$B$，查询最短路，如果最短路变化了，那么$[l,mid]$中一定有这样的边，于是先把$[l,mid]$设回$A$，再去$[l,mid]$中寻找答案，否则它就在$[mid+1,r]$了
假设我们找出来的边是$(x,y)$，我们用这条边构造两个不相交的集合$S_1,S_2$（以下的距离都是边权为$1$的距离）
如果一个点$u$满足$dis_{u,x}<dis_{u,y}$，那么$u\in S_1$，如果$u$满足$dis_{u,x}\gt dis_{u,y}$，那么$u\in S_2$
在$S_1$中以$x$为根构造bfs树，在$S_2$中以$y$为根构造bfs树，那么$S\rightarrow T$一定存在一条最短路是只经过树边和$(x,y)$的
将非树边设为$B$，将树边和$(x,y)$设为$A$，那么接下来要做的事情就和第二个部分分的最后一步一样了
总时间复杂度$O\left(m(\log m+\log n)\right)$，调用次数为$1+\left\lceil\log_2m\right\rceil+2\left\lceil\log_2\frac n2\right\rceil$，刚好是$50$，但官方数据好像并没有卡满...
神仙图论题...
#include"highway.h"#include#include #include using namespace std;typedef long long ll;const int inf=2147483647;int abs(int x){return x>0?x:-x;}int h[90010],nex[260010],to[260010],id[260010],M,n,m;void add(int a,int b,int c){ M++; to[M]=b; id[M]=c; nex[M]=h[a]; h[a]=M;}int q[90010],d1[90010],d2[90010];void getdis(int*d,int x){ int head,tail,i; for(i=1;i<=n;i++)d[i]=inf; head=tail=1; q[1]=x; d[x]=0; while(head<=tail){ x=q[head++]; for(i=h[x];i;i=nex[i]){ if(d[x]+1