CF2253E
2026-08-08 09:11:00
发布于：广东
27阅读
0回复
0点赞
草！！！！！！！！！！！！！！！卡lamda函数的来了，MLE！！！！！改全局AC了，涨分失败。。。
注意到这个直径限制为奇数（记为），那么就是说这条直径的中心部分一定是一条线，这条线连接着两个点。
我们考虑将这两边子树拆开，记，所以我们分别在这两个子树中跑，若枚举到一个深度，看在这个深度下，有没有相重合的，如果有这个就算一个答案。
这样我们处理出两个子树答案集合，，排序去重即可。
这样我们就做完了。
再让你们看看MLE和AC代码，才能知道赛场上我多悲催。。。
MLE：
#pragma comment(linker, "/STACK:268435456")
#include<bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
using lb = long double;
void Main() {
int n; cin>>n;
vec<vec<int>> adj(n+1);
for (int i=1;i<n;++i){
int u,v;
cin>>u>>v;
adj[u].pb(v);
adj[v].pb(u);
}
vec<int> fa(n+1,0),dis(n+1,0);
auto dfs=[&](auto &self,int u,int fath,int d)->int{
fa[u]=fath,dis[u]=d;
int ma=u;
for (int v:adj[u]){
if (v==fath) continue;
int can=self(self,v,u,d+1);
if (dis[can]>dis[ma]){
ma=can;
}
}
return ma;
};
int ma1=dfs(dfs,1,-1,0);
int ma2=dfs(dfs,ma1,-1,0);
vec<int> path;
for (int cur=ma2;~cur;cur=fa[cur]){
path.pb(cur);
}
int half=(dis[ma2]-1)/2;
int eu=path[half],ev=path[half+1];
vec<int> su,sv;
auto dfs2=[&](auto &self,int u,int fath,int dpth,int no_p,int ma_d,vec<int>& s)->int{
int dd=dpth,cnt=0;
for (int v:adj[u]){
if (v==fath||v==no_p) continue;
int res=self(self,v,u,dpth+1,no_p,ma_d,s);
dd=max(dd,res);
if (res==ma_d) ++cnt;
}
if (cnt>=2) s.pb(dpth);
return dd;
};
su.pb(half);
dfs2(dfs2,eu,-1,0,ev,half,su);
sv.pb(half);
dfs2(dfs2,ev,-1,0,eu,half,sv);
vec<int> ans;
for (auto sz1:su){
for (int sz2:sv){
ans.pb(sz1+sz2+1);
}
}
sort(ans.begin(),ans.end());
ans.erase(unique(ans.begin(),ans.end()),ans.end());
cout<<ans.size()<<' ';
for (auto i:ans) cout<<i<<' ';
cout<<endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int Test = 1;
cin >> Test;
while (Test--) CZW::Main();
return 0;
}
AC：
#include<bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
using lb = long double;
constexpr int N = 1e6+5;
vec<int> adj[N];
int fa[N], dis[N];
int dfs(int u, int fath, int d) {
fa[u] = fath, dis[u] = d;
int ma = u;
for (int v : adj[u]) {
if (v == fath) continue;
int can = dfs(v, u, d + 1);
if (dis[can] > dis[ma]) {
ma = can;
}
}
return ma;
}
int dfs2(int u, int fath, int dpth, int no_p, int ma_d, vec<int> &s) {
int dd = dpth, cnt = 0;
for (int v : adj[u]) {
if (v == fath || v == no_p) continue;
int res = dfs2(v, u, dpth + 1, no_p, ma_d, s);
dd = max(dd, res);
if (res == ma_d) ++cnt;
}
if (cnt >= 2) s.pb(dpth);
return dd;
}
void Main() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) adj[i].clear(), fa[i] = 0, dis[i] = 0;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
int ma1 = dfs(1, -1, 0), ma2 = dfs(ma1, -1, 0);
vec<int> path;
for (int cur = ma2; ~cur; cur = fa[cur]) {
path.pb(cur);
}
int half = (dis[ma2] - 1) / 2;
int eu = path[half], ev = path[half + 1];
vec<int> su, sv;
su.pb(half);
dfs2(eu, -1, 0, ev, half, su);
sort(su.begin(), su.end());
su.erase(unique(su.begin(),su.end()),su.end());
sv.pb(half);
dfs2(ev, -1, 0, eu, half, sv);
sort(sv.begin(),sv.end());
sv.erase(unique(sv.begin(),sv.end()),sv.end());
vec<int> ans;
for (auto sz1 : su) {
for (int sz2 : sv) {
ans.pb(sz1 + sz2 + 1);
}
}
sort(ans.begin(), ans.end());
ans.erase(unique(ans.begin(), ans.end()), ans.end());
cout << ans.size() << ' ';
for (auto i : ans) cout << i << ' ';
cout << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int Test = 1;
cin >> Test;
while (Test--) CZW::Main();
return 0;
}
@cjdst 做出D的大佬教我C++
有帮助，赞一个