主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
题解:P10238 [yLCPC2024] F. PANDORA PARADOXXX
最后更新于 2025-07-31 08:12:18
作者
fish_love_cat
分类
题解
题解
P10238
复制 Markdown
查看原文
删除文章
更新内容
巨大[细节](https://www.luogu.com.cn/discuss/1118423)题! --- 考虑倒着做变成加边,有经典结论: > 合并后新树的任意直径端点,必然是合并前某棵树中某条直径的端点。 :::::info[证明] 合并一定会增加一条边 $(u,v)$。 如果新的直径不过这条边,那么直径仍然是某棵树原本的直径,原命题必然成立。 如果经过这条边,那么就变成要证明在 $u$ 原本所在的树中离它最远的点是该树某条直径的端点,$v$ 同理。 于是就变成了证明这么一个命题: > 到任意点距离最远的点必是树的一条直径的端点。 这个结论是广为人知的,最常见的应用就是求树的直径,所以证明略去。 所以原命题成立。 ::::: 于是就好做了: 先搜一遍把每个点的深度求出来,然后求距离可以转变成求 LCA,这个是板子不说了。 接着并查集维护连通。 对于每个连通块先求直径,并记录端点。 根据结论合并的时候只有四个可能的端点,组合一下总共有六种情况,分讨就做完了,模拟上述过程即可。 除了容易写挂以外没有任何难度,鉴定为大模拟。 坑点见前言。 --- [AC 记录](https://www.luogu.com.cn/record/227684492)及代码: ```cpp // 途切れていた止まっていた日々が // 戛然而止 停滞不前的时光 // 輝くよな想い出に // 化身流光溢彩的回忆 // 埋められていくの // 被时间沙漏不断埋藏 #include<bits/stdc++.h> #define int long long #define mk make_pair #define pb push_back using namespace std; int fa[100005]; int find(int x){ return(x==fa[x]?x:fa[x]=find(fa[x])); } vector<pair<int,pair<int,int> > >ve[100005]; int mi[25][100005],dfn[100005],dfnn; int get(int u,int v){ if(dfn[u]<dfn[v])return u; else return v; } void dfs(int id,int f){ mi[0][dfn[id]=++dfnn]=f; for(pair<int,pair<int,int> > it:ve[id]) if(it.first!=f)dfs(it.first,id); } int lca(int u,int v){ if(u==v)return u; if((u=dfn[u])>(v=dfn[v])) swap(u, v); int d=__lg(v-u++); return get(mi[d][u],mi[d][v-(1<<d)+1]); } int q[100005]; bool use[100005]; bool vis[100005]; int dep,depid; pair<int,int>zj[100005]; int ret; int dis[100005]; void dfs1(int x,int fa){ for(int i=0;i<ve[x].size();i++){ if(ve[x][i].first==fa)continue; dis[ve[x][i].first]=dis[x]+ve[x][i].second.first; dfs1(ve[x][i].first,x); } } void dfs2(int x,int fath,int dp,bool op){ vis[x]=op; if(dp>dep)dep=dp,depid=x; for(int i=0;i<ve[x].size();i++){ if(vis[ve[x][i].first])continue; if(use[ve[x][i].second.second])continue; if(ve[x][i].first==fath)continue; if(fa[find(ve[x][i].first)]!=find(x)) fa[find(ve[x][i].first)]=find(x); dfs2(ve[x][i].first,x,dp+ve[x][i].second.first,op); } } int jl(int x,int y){ return dis[x]+dis[y]-2*dis[lca(x,y)]; } vector<pair<int,int> >qwq; void init(int n); void solve(){ int n,Q; cin>>n>>Q; init(n); for(int i=1;i<n;i++){ int u,v,w; cin>>u>>v>>w; ve[u].pb(mk(v,mk(w,i))); ve[v].pb(mk(u,mk(w,i))); qwq.push_back(mk(u,v)); } dfs1(1,0); dfs(1,0); for(int i=1;i<=__lg(n);i++) for(int j=1;j<=n-(1<<i)+1;j++) mi[i][j]=get(mi[i-1][j],mi[i-1][j+(1<<(i-1))]); for(int i=1;i<=Q;i++) cin>>q[i],use[q[i]]=1; reverse(q+1,q+1+Q); for(int i=1;i<=n;i++){ if(vis[i])continue; dep=-1; dfs2(i,0,0,0); dep=-1; zj[find(i)].first=depid; dfs2(depid,0,0,1); zj[find(i)].second=depid; ret=max(ret,dep); } vector<int>out; for(int i=1;i<=Q;i++){ out.push_back(ret); if(i==Q)break; int x1=jl(zj[find(qwq[q[i]].first)].first, zj[find(qwq[q[i]].second)].first); int x2=jl(zj[find(qwq[q[i]].first)].first, zj[find(qwq[q[i]].second)].second); int x3=jl(zj[find(qwq[q[i]].first)].second, zj[find(qwq[q[i]].second)].first); int x4=jl(zj[find(qwq[q[i]].first)].second, zj[find(qwq[q[i]].second)].second); int x5=jl(zj[find(qwq[q[i]].first)].first, zj[find(qwq[q[i]].first)].second); int x6=jl(zj[find(qwq[q[i]].second)].first, zj[find(qwq[q[i]].second)].second); int maxx=max({x1,x2,x3,x4,x5,x6}); if(maxx==x1) zj[find(qwq[q[i]].second)]=mk(zj[find(qwq[q[i]].first)].first, zj[find(qwq[q[i]].second)].first); else if(maxx==x2) zj[find(qwq[q[i]].second)]=mk(zj[find(qwq[q[i]].first)].first, zj[find(qwq[q[i]].second)].second); else if(maxx==x3) zj[find(qwq[q[i]].second)]=mk(zj[find(qwq[q[i]].first)].second, zj[find(qwq[q[i]].second)].first); else if(maxx==x4) zj[find(qwq[q[i]].second)]=mk(zj[find(qwq[q[i]].first)].second, zj[find(qwq[q[i]].second)].second); else if(maxx==x5) zj[find(qwq[q[i]].second)]=mk(zj[find(qwq[q[i]].first)].first, zj[find(qwq[q[i]].first)].second); else if(maxx==x6) zj[find(qwq[q[i]].second)]=mk(zj[find(qwq[q[i]].second)].first, zj[find(qwq[q[i]].second)].second); fa[find(qwq[q[i]].first)]=find(qwq[q[i]].second); ret=max(ret,maxx); } reverse(out.begin(),out.end()); for(int i=0;i<out.size();i++) cout<<out[i]<<'\n'; } signed main(){ int t; cin>>t; while(t--)solve(); return 0; } void init(int n){ qwq.clear(); ret=0; for(int i=1;i<=n;i++){ zj[i]=mk(0,0); dis[i]=0; fa[i]=i; for(int j=0;j<25;j++) mi[j][i]=0; q[i]=use[i]=vis[i]=dfn[i]=0; ve[i].clear(); } dep=-1; depid=dfnn=0; qwq.push_back(mk(0,0)); } // 忘れないよ覚えてるよこの瞬間を // 那难以忘怀的瞬间我时刻谨记在心 // 終わりに残す言葉は // 尘埃落定时相互嘱咐的话语 // 「また会おうね」ふたりの約束 // 竟是「有缘再见」两人的约定 // Last Diary ```
正在渲染内容...
点赞
0
收藏
0