1.最长路程
考虑一个简单的85分做法：维护若干条链的集合\(S\)。
每次从\(S\)中取出\(3\)条链，设他们的一个端点（任意取）为\(a,b,c\)。
查询\((a,b)\)，如果联通则合并\((a,b)\)对应的链。
如果不连通则查询\((b,c)\)，如果联通则合并\((b,c)\)对应的链。否则由题目条件，\((a,c)\)必定有边，合并\((a,c)\)对应的链。
重复以上过程指导剩下最多两条链。
设第一条链的端点为\((x1,y1)\)，第二条链的为\((x2,y2)\)。
如果\(\{x1,y1\},{x2,y2}\)之间有边，则通过第一条链，这条边，第二条链显然能找到一条长度为\(n\)的路径。
否则由于\((x1,x2)\)和\((x1,y2)\)都没有边，\((x1,y1),(x2,y2)\)都有边。
此时查询两条链的节点之间有没有边。如果没有，则返回长度更大的链作为答案。
如果有，可以二分出这条边，之后容易构造方案。
操作次数最坏情况下为\(2n+\log_2(n^2)\)次。
考虑优化这个做法。
优化1：题目由于没说交互库是自适应的，可以随机化。
上面每次取出的链可以随机取。
然而这样子没法过。
优化2：考虑修改上面的做法。每次随机取出\(3\)个孤立点，如果\((a,b)\)没有边，则可以再取出一条长度为\(1\)的链\(d\)。
则根据题目的性质，\((b,c),(a,c)\)以及\((b,d),(a,d)\)之间必定存在边，可以用这两条边合并这些点。
重复以上过程直到图中最多有\(3\)个孤立点，然后运行85分做法。
思路比较简单，但是代码很难写。
#include<bits/stdc++.h>
#define sz 300
#include"longesttrip.h"
using namespace std;
int f[sz],c[sz],d[sz],vi[sz];
vector<int>ci[sz],vc;
int fd(int x){
return f[x]==x?x:f[x]=fd(f[x]);
}
void mg(int x,int y){
int xx=fd(x),yy=fd(y);
f[yy]=xx;
reverse(ci[xx].begin(),ci[xx].end());
for(int i=0;i<ci[yy].size();i++)
ci[xx].push_back(ci[yy][i]);
}
int qu(int x,int y){
vector<int>v1,v2;
v1.push_back(x);
v2.push_back(y);
return are_connected(v1,v2);
}
vector<int> ef(vector<int>x,vector<int>y,int t){
if(t&&!are_connected(x,y)){
vector<int>v;
return v;
}
int ok=0;
while(1){
vector<int>g1,g2;
if(y.size()==1){
swap(x,y);
ok=1;
}
if(x.size()==1){
int ss=y.size()/2;
for(int i=0;i<ss;i++)
g2.push_back(y[i]);
g1.push_back(x[0]);
if(are_connected(g1,g2)){
if(ss==1){
vector<int>av;
if(!ok){
av.push_back(x[0]);
av.push_back(y[0]);
}
else{
av.push_back(y[0]);
av.push_back(x[0]);
}
return av;
}
else
y=g2;
}
else{
if(y.size()-ss==1){
vector<int>av;
if(!ok){
av.push_back(x[0]);
av.push_back(y[1]);
}
else{
av.push_back(y[1]);
av.push_back(x[0]);
}
return av;
}
g2.clear();
for(int i=ss;i<y.size();i++)
g2.push_back(y[i]);
y=g2;
}
}
else{
int ss=x.size()/2;
for(int i=0;i<ss;i++)
g1.push_back(x[i]);
g2=y;
if(are_connected(g1,g2))
x=g1;
else{
g1.clear();
for(int i=ss;i<x.size();i++)
g1.push_back(x[i]);
x=g1;
}
}
}
}
vector<int> longest_trip(int n,int k){
vc.clear();
for(int i=0;i<n;i++){
vi[i]=0;
c[i]=f[i]=i;
ci[i].clear();
ci[i].push_back(i);
}
random_shuffle(c,c+n);
int po=0,ct=n,p1=-1,p2=-1;
while(po+3<n){
int v1=ci[fd(c[po])][0],v2=ci[fd(c[po+1])][0];
if(qu(v1,v2)){
mg(v1,v2);
ct--;
po+=2;
}
else{
int v3=ci[fd(c[po+2])][0],v4=ci[fd(c[po+3])][0];
if(qu(v1,v3))
mg(v1,v3);
else
mg(v2,v3);
if(qu(v1,v4))
mg(v1,v4);
else
mg(v2,v4);
ct-=2;
po+=4;
}
}
while(ct>2){
random_shuffle(c,c+n);
int xx=fd(c[0]),yy=fd(c[1]),zz=fd(c[2]);
if(xx==yy||yy==zz||zz==xx)
continue;
d[0]=ci[xx][0];
d[1]=ci[yy][0];
d[2]=ci[zz][0];
random_shuffle(d,d+3);
if(qu(d[0],d[1]))
mg(d[0],d[1]);
else if(qu(d[1],d[2]))
mg(d[1],d[2]);
else
mg(d[2],d[0]);
ct--;
}
int cn=0;
for(int i=0;i<n;i++)
if(!vi[fd(i)]){
cn++;
vc.push_back(fd(i));
vi[fd(i)]=1;
}
vector<int>g1,g2;
g1.push_back(ci[vc[0]][0]);
if(ci[vc[0]][0]!=ci[vc[0]].back())
g1.push_back(ci[vc[0]].back());
g2.push_back(ci[vc[1]][0]);
if(ci[vc[1]][0]!=ci[vc[1]].back())
g2.push_back(ci[vc[1]].back());
vector<int>ans=ef(g1,g2,1);
if(!ans.empty()){
if((ans[1]==g2[1]&&ans[0]==g1[1]))
reverse(ci[vc[1]].begin(),ci[vc[1]].end());
else if((ans[1]==g2[0]&&ans[0]==g1[0]))
reverse(ci[vc[0]].begin(),ci[vc[0]].end());
else if(ans[0]==g1[0]&&ans[1]==g2[1]){
reverse(ci[vc[1]].begin(),ci[vc[1]].end());
reverse(ci[vc[0]].begin(),ci[vc[0]].end());
}
for(int i=0;i<ci[vc[1]].size();i++)
ci[vc[0]].push_back(ci[vc[1]][i]);
return ci[vc[0]];
}
else{
if(!are_connected(ci[vc[0]],ci[vc[1]])){
if(ci[vc[0]].size()>ci[vc[1]].size())
swap(vc[0],vc[1]);
return ci[vc[1]];
}
ans=ef(ci[vc[0]],ci[vc[1]],0);
int xx=ans[0],yy=ans[1];
if(xx<yy)
swap(xx,yy);
vector<int>t;
int p=0;
for(int i=0;i<ci[vc[0]].size();i++)
if(ci[vc[0]][i]==ans[0])
p=i;
p++;
if(p>=ci[vc[0]].size())
p=0;
for(int i=0;i<ci[vc[0]].size();i++){
t.push_back(ci[vc[0]][p]);
p++;
if(p>=ci[vc[0]].size())
p=0;
}
for(int i=0;i<ci[vc[1]].size();i++)
if(ci[vc[1]][i]==ans[1])
p=i;
for(int i=0;i<ci[vc[1]].size();i++){
t.push_back(ci[vc[1]][p]);
p++;
if(p>=ci[vc[1]].size())
p=0;
}
return t;
}
}