题意:
给出一个树,每条边都有权值。定义两个点之间的距离为两点路径上的边的权值的g c d。
每次可以询问一个点集,答案返回该点集中任意两个点之间距离的最大值。
求两点使得距离是最大的。
思路:
第一个性质就是由于距离是边的权值取g c d,所以单条边的距离是最大的,也就是说最后的答案的点是相邻的。
首先我们可以询问所有的点,得到一个最大值a n s,接下来只需要查找a n s是由哪两个点连接形成的就好了。
还能够询问11次,而n = 1000,看能否用二分来解。
将树上问题转化为序列问题可以借助欧拉序,欧拉序有很多种,可以根据实际情况写。对于本题最好是将每条边和两个端点都枚举出来。
可以这样:
void dfs(int u,int fa){ for(int tt:g[u]){ if(tt==fa) continue; seq[++top]=tt;//欧拉序有很多种 dfs(tt,u); seq[++top]=u; } }
得到的序列是[ 1 , 2 , 3 , 2 , 4 , 2 , 1 , 5 , 6 , 5 , 1 ]
这样每条边的端点都是序列里相邻的两个点了。
对答案进行二分,假设最大值的边是由下标为l , r的两个端点构成。
那么只需要查询下标为[ 1 , m i d ]的点集中的最大值,如果说该最大值等于a n s的话,说明边在左边区间;反之,说明边在右边区间。继续二分就可以了。
由于得到的序列中每个点出现的次数不是唯一的,所以在查询的时候要进行去重。
还有一个小tips,交互题如果不使用f f l u s h ( s t d o u t ) ; 的话,可以输出的时候用c o u t < < … … < < e n d l cout<<……<
参考视频
巨巨的E都更完了,我的D才刚补完
参考博客
代码:
// Problem: D. Hemose in ICPC ? // Contest: Codeforces - Codeforces Round #746 (Div. 2) // URL: https://codeforces.com/contest/1592/problem/D // Memory Limit: 256 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=1e6+7,maxm=1e6+7,mod=1e9+7; int n,seq[maxn],top,ans; vector<int>g[maxn]; vector<int>q; void dfs(int u,int fa){ for(int tt:g[u]){ if(tt==fa) continue; seq[++top]=tt;//欧拉序有很多种 dfs(tt,u); seq[++top]=u; } } int query(){ sort(q.begin(),q.end()); q.erase(unique(q.begin(),q.end()),q.end()); cout<<"? "<<(int)q.size()<<" "; for(int i=0;i<q.size();i++){ cout<<q[i]<<" "; } cout<<endl; q.clear(); int ans;cin>>ans; return ans; } int main(){ cin>>n; for(int i=1;i<n;i++){ int u,v;cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } seq[++top]=1; dfs(1,0); for(int i=1;i<=n;i++) q.push_back(i); ans=query(); int l=1,r=top,res; while(l<r-1){ int mid=(l+r)/2; for(int i=1;i<=mid;i++) q.push_back(seq[i]); int now=query(); if(now==ans) r=mid; else l=mid; } cout<<"! "<<seq[l]<<" "<<seq[r]<<endl; // printf("! %d %d\n",seq[l],seq[r]); return 0; }