Tree Diameter
传送门
题意：给定整数
-
给每条边赋
[1,10^9] 的权，求带权直径。 -
给定两个编号，回答这两条边的距离。
两种操作都不能超过
首先，这类问树的形态的题，有一个很常用的思路：一层一层做。
也就是先求出每个点的深度，再一层一层确定树的形态。
由于我们只能知道关于边的信息，所以在边的角度考虑问题。
首先随便取一条边作为根，然后求出每条边的深度，可以通过
然后按深度的顺序，一层一层确定树的形态。
首先考虑确定第一层的形态，也就是确定每条边是在左半边还是右半边。
考虑我们可以用第一种操作得到什么信息，可以通过给一个边集的边权整体乘上
对于第一层的第一个点，显然接在哪里都是无所谓的。
对于后面的点，考虑如下构造：
其中，蓝色的点是已经确定在左边的任意一个点，红色的点是当前要确定的边对应的点。
可以发现，将图中的三条边设置为
于是可以通过一次询问确定每条边在哪一边，从而确定第一层。
接下来考虑在已知上一层的情况下构造下一层。
问题在于如何求出来每条边接在哪个点下边。
考虑如下构造：
也就是给上一层的每个点和父亲的连边设置为
定义 INF 为比
也就是我们用求出来的直径减去 INF，再减去
但是会有一种特殊情况：当前的边连到的点是编号最大的点。
此时，直径会经过编号最大和次大的点。
也就是，用上述方法得到的编号若不是编号次大的点，则可以确定。
否则，这条边连到的点可能是最大和次大的点之一。
考虑如何确定这条边具体连到哪个点。
若编号最大和次大的点同时在右边，则可以考虑如下构造：
把要确定的边的边权设置为 INF，让直径减去
若编号最大和次大的点分别在两边，则可以先找到一个已经确定的点，使得这个点不是这两个点中任何一个点的祖先，把这个点和父亲的连边设为 INF，最大和次大的点和父亲的连边同上，要确定的边设为 INF，就可以用同上的方法确定。
如果找不到这么一个点，则整棵树一定由两条对称的链构成。此时可以发现，把这条边接在哪里都是一样的，所以随便选一个即可。
通过上述构造，每条边加入时最多需要
考虑继续优化，能否一次询问确定一条边？
延续上面的思路，如果我们能找到一个已经确定为叶子的点，则可以进行下图的构造：
套用上文的做法，可以发现由于红点下方一定不再接其它点，所以这种构造下不再会产生冲突，也就是可以通过
但是可能不存在这样的点。
假如我们已经确定了这一层的第一个点，则可以将这个确定的点作为上图的红点，但是不同的地方是当红点和蓝点接到同一个点上时，求出的直径减去两个 INF 后为
现在，问题在于如何确定每一层的第一个点。
考虑能否通过两次操作同时问出来两个点。
考虑如下构造：
其中，Inf 是数量级介于
我们想同时确定红点和蓝点相连的边。
可以发现，存在以下四种情况：
- 红点和蓝点都在左侧。
此时，我们知道红点和蓝点的编号和，只需要将根设为 INF，蓝点设为 INF，不考虑红点，只保留上一层在左侧的点和父亲的连边，则可以求出蓝点连在哪个点下面，然后作差得到红点连接的点的编号。
- 红点和蓝点都在右侧。
同第一种情况。
- 红点和蓝点分别在两侧。
此时，由于我们设置了两个不同数量级的极大值，所以可以直接求出来两个点连接的两个点的编号，但是不知道对应关系。
只需要知道红点和蓝点哪个在左侧，哪个在右侧即可，也就是要判断红点是否在左侧。考虑如下构造：
如果红点在左侧，则直径为 INF，否则直径为两倍 INF。
但是还会有右侧只有一个点的情况，此时可以把判断放到左侧。如果两侧都只有一个点，则整棵树一定由两条相同的链构成。否则就说明这棵树至少有一个已经确定为叶子的节点，则会在上文中被解决。此时，接在哪里都是无所谓的。
- 红点和蓝点接在同一个点上。
此时，可以把这两个点合并，放到后面一起确定。
还有最后一种情况就是这一层所有点都接在同一个点上。
此时直接套用上文的
综上，我们用不超过
最后还需要注意一个点：由于我们用到了
#include <bits/stdc++.h>
#define int long long
using namespace std;
int ask1(vector<signed>q){
cout<<"? 1 ";
for(auto c:q)cout<<c<<" ";
cout<<endl;
int x;
cin>>x;
return x;
}
int ask2(int a,int b){
cout<<"? 2 "<<a+1<<" "<<b+1<<endl;
int x;
cin>>x;
return x;
}
const int N=1e3+5,T=1000,G=1e6,B=1e9;
int dep[N],idx=2,dy[N],fa[N],bk[N],bh[N],ok[N];
vector<pair<signed,signed> >rs;
vector<int>q,jl;
vector<pair<signed,signed> >solve(signed t,signed n,signed lim1,signed lim2){
vector<signed>g;
auto sets=[&](int x,int y){
g[x-1]=y;
};
auto upt=[&](int x){
while(x){
bk[x]=1;
x=fa[x];
}
};
auto init=[&](){
for(int i=0;i<n-1;i++)g[i]=1;
};
for(int i=2;i<n;i++)dep[i]=ask2(0,i-1);
int tmp=0;
bh[1]=1;bh[2]=2;
g.resize(n-1);
rs.push_back({1,2});
for(int i=2;i<n;i++){
if(dep[i]==0){
if(!tmp){
idx++;
rs.push_back({2,idx});
fa[idx]=2;
bh[idx]=2;
dy[i]=idx;
tmp=i;
}else{
init();
sets(1,T);
sets(tmp,T);
sets(i,T);
int sm=ask1(g);
idx++;
dy[i]=idx;
if(sm>=3*T){
rs.push_back({1,idx});
fa[idx]=1;
bh[idx]=1;
}else{
rs.push_back({2,idx});
fa[idx]=2;
bh[idx]=2;
}
}
}
}
for(int i=1;i<=n;i++){
auto add=[&](int a,int b){
idx++;
dy[a]=idx;
fa[idx]=b;
bh[idx]=bh[b];
rs.push_back({b,idx});
};
auto Solve=[&](int j){
init();
for(int k=1;k<=jl.size();k++)sets(jl[k-1],k*T);
sets(j,B);
int sm=ask1(g);
sm-=B;
sm/=T;
int a=jl.back(),b=jl[sm-jl.size()-1];
if(sm-jl.size()!=jl.size()-1){
idx++;
rs.push_back({dy[b],idx});
fa[idx]=dy[b];
bh[idx]=bh[dy[b]];
dy[j]=idx;
return;
}
if(bh[dy[a]]==bh[dy[b]]){
init();
sets(j,B);
sets(a,T);
sets(b,2*T);
sets(1,B);
int sm=ask1(g);
sm-=2*B;
idx++;
if(sm>=2*T){
rs.push_back({dy[b],idx});
fa[idx]=dy[b];
bh[idx]=bh[dy[b]];
dy[j]=idx;
}else{
rs.push_back({dy[a],idx});
fa[idx]=dy[a];
bh[idx]=bh[dy[a]];
dy[j]=idx;
}
return;
}
memset(bk,0,sizeof(bk));
upt(dy[a]);upt(dy[b]);
int wz=0;
for(int k=2;k<n;k++){
if(dep[k]>=i)continue;
if(!bk[dy[k]]){
wz=k;
break;
}
}
if(!wz){
idx++;
rs.push_back({dy[a],idx});
fa[idx]=dy[a];
bh[idx]=bh[dy[a]];
dy[j]=idx;
return;
}else{
init();
sets(wz,B);
sets(1,B);
sets(j,B);
int sm=ask1(g);
if(sm>=3*B){
if(bh[dy[wz]]!=bh[dy[a]]){
idx++;
rs.push_back({dy[a],idx});
fa[idx]=dy[a];
bh[idx]=bh[dy[a]];
dy[j]=idx;
}else{
idx++;
rs.push_back({dy[b],idx});
fa[idx]=dy[b];
bh[idx]=bh[dy[b]];
dy[j]=idx;
}
}else{
if(bh[dy[wz]]==bh[dy[a]]){
idx++;
rs.push_back({dy[a],idx});
fa[idx]=dy[a];
bh[idx]=bh[dy[a]];
dy[j]=idx;
}else{
idx++;
rs.push_back({dy[b],idx});
fa[idx]=dy[b];
bh[idx]=bh[dy[b]];
dy[j]=idx;
}
}
}
};
auto pd=[&](int j){
init();
sets(j,B);
int sm1=0,sm2=0;
for(int k=1;k<=jl.size();k++){
if(bh[dy[jl[k-1]]]==1)sm1++;
else sm2++;
}
if(sm1>1){
for(int k=1;k<=jl.size();k++){
if(bh[dy[jl[k-1]]]==1)sets(jl[k-1],T);
}
return ask1(g)-B>=2*T;
}else if(sm2>1){
for(int k=1;k<=jl.size();k++){
if(bh[dy[jl[k-1]]]==2)sets(jl[k-1],T);
}
return ask1(g)-B<2*T;
}else return true;
};
memset(ok,0,sizeof(ok));
for(int j=3;j<=idx;j++)ok[fa[j]]=1;
int ww=0;
for(int j=2;j<n;j++){
if(dep[j]>=i-1)continue;
if(ok[dy[j]])continue;
ww=j;
}
jl.clear();
for(int j=2;j<n;j++){
if(dep[j]==i-1){
jl.push_back(j);
}
}
if(!jl.size())break;
if(jl.size()==1){
for(int j=2;j<n;j++){
if(dep[j]==i){
idx++;
rs.push_back({dy[jl[0]],idx});
fa[idx]=dy[jl[0]];
bh[idx]=bh[fa[idx]];
dy[j]=idx;
}
}
continue;
}
random_shuffle(jl.begin(),jl.end());
int tmp=0;
vector<int>lj;
for(int j=2;j<n;j++){
if(dep[j]==i){
if(!tmp){
// cout<<"d"<<j<<" "<<ww<<endl;
if(ww){
tmp=j;
init();
for(int k=1;k<=jl.size();k++){
sets(jl[k-1],k*T);
// cout<<k<<" "<<jl[k-1]<<" "<<dy[jl[k-1]]<<endl;
}
sets(j,B);
sets(ww,B);
int sm=ask1(g);
sm-=2*B;
sm/=T;
int b=jl[sm-1];
// cerr<<sm<<"--"<<b<<endl;
idx++;
rs.push_back({dy[b],idx});
fa[idx]=dy[b];
bh[idx]=bh[dy[b]];
dy[j]=idx;
continue;
}
if(!lj.size()){
lj.push_back(j);
continue;
}
init();
int T=n-jl.size(),G=2*T*jl.size();
for(int k=1;k<=jl.size();k++){
if(bh[dy[jl[k-1]]]==1)sets(jl[k-1],k*T);
else sets(jl[k-1],k*G);
}
int lst=lj[0];
sets(j,B);
sets(lst,B);
int sm=ask1(g);
sm-=2*B;
if(sm<T){
lj.push_back(j);
continue;
}else if(sm<G){
sm/=T;
init();
for(int k=1;k<=jl.size();k++){
if(bh[dy[jl[k-1]]]==1)sets(jl[k-1],k*T);
}
sets(j,B);
sets(1,B);
int sms=ask1(g);
sms-=2*B;
sms/=T;
int to1=dy[jl[sms-1]],to2=dy[jl[sm-sms-1]];
add(j,to1);
for(auto c:lj){
add(c,to2);
}
lj.clear();
}else if(sm%G<T){
sm/=G;
init();
for(int k=1;k<=jl.size();k++){
if(bh[dy[jl[k-1]]]==2)sets(jl[k-1],k*T);
}
sets(j,B);
sets(1,B);
int sms=ask1(g);
sms-=2*B;
sms/=T;
int to1=dy[jl[sms-1]],to2=dy[jl[sm-sms-1]];
add(j,to1);
for(auto c:lj)add(c,to2);
lj.clear();
}else{
int s1=sm%G/T,s2=sm/G,to1=dy[jl[s1-1]],to2=dy[jl[s2-1]];
// cerr<<to1<<"--"<<to2<<endl;
if(pd(j)){
add(j,to1);
for(auto c:lj)add(c,to2);
}else{
add(j,to2);
for(auto c:lj)add(c,to1);
}
lj.clear();
}
tmp=j;
}else{
init();
sets(tmp,B);
sets(j,B);
int tt=0;
for(int k=1;k<=jl.size();k++){
sets(jl[k-1],k*T);
if(dy[jl[k-1]]==fa[dy[tmp]])tt=k;
}
int sm=ask1(g),to;
sm-=2*B;
sm/=T;
if(!sm){
to=fa[dy[tmp]];
}else{
sm-=tt;
to=dy[jl[sm-1]];
}
idx++;
rs.push_back({to,idx});
fa[idx]=to;
dy[j]=idx;
bh[idx]=bh[to];
}
}
}
if(lj.size()){
Solve(lj[0]);
int tmp=fa[dy[lj[0]]];
for(int j=1;j<lj.size();j++)add(lj[j],tmp);
}
}
//for(auto [a,b]:rs)cerr<<a<<"-"<<b<<endl;
return rs;
}
signed main(){
int n;
cin>>n;
auto rs=solve(0,n,0,0);
cout<<"!"<<endl;
for(auto [a,b]:rs)cout<<a<<" "<<b<<"\n";
}