联盟
题目描述
\(\text{G}\) 国周边的 \(n\) 个小国家构成一个联盟以抵御 \(\text{G}\) 国入侵, 为互相支援,他们建立了\(n−1\) 条双向通路, 使得任意两个国家可以经过通路相互到达.
当一个国家受到攻击时, 所有其它国家都会沿着最短路径前往这个国家进行支援，经过每条通路所需的时间均为\(1\). 定义一个国家的危险程度为所有国家全部赶到需要的最短时间, 联盟的危险程度为所有国家的危险程度的最大值.
为了降低危险程度, 联盟决定断开一条通路并任意连接一条通路, 使得危险程度尽可能小, 并要求改建完成之后任意两个国家可以经过通路互相到达.
他们决定让你来设计方案, 你需要告知在最优方案中可能断开哪些边,并给出任意一组最优方案.
输入输出格式
输入格式
第一行一个正整数\(n\).
接下来 \(n-1\) 行每行两个正整数, 表示一条\(u_i\), \(v_i\) 之间的边.
输出格式
输出第一行一个整数表示最小危险程度.
第二行一个整数 \(k\), 表示可能被断开的边的数量, 接下来 \(k\) 个数, 表示
可能断开的边的编号, 按升序输出.
接下来一行四个正整数表示一组最优方案, 分别表示断开和新建的边的端点, 只需给出任意一组合法的方案即可.
提示
对于\(20\%\)的数据,\(n\le 30\).
对于\(40\%\)的数据,\(n\le 300\).
对于\(60\%\)的数据,\(n\le 3000\).
对于\(100\%\)的数据,\(n\le 300000\).
如果你的答案仅第一行正确, 你可以获得 \(25\%\) 的分数,
如果你的答案仅前两行正确, 你可以获得 \(50\%\) 的分数,
为保证得到部分分请确保提交程序的输出格式符合题目要求.
其实思维没什么难度。
枚举断边，处理出两颗分开的树的直径，求一下新的直径就可以了
已知两棵树的直径分别为\(a,b\)，用一条边连接这两颗树得到的最小直径是\(max(a,b,\lceil \frac{a}{2} \rceil +\lceil \frac{b}{2} \rceil +1)\)，就是连接这个直径中间的点
细节非常多，写起来很恶心，可以练练代码能力
考场上硬是没调出来爆0了。。。
Code:
#include <cstdio>
#include <algorithm>
#include <vector>
const int N=3e5+10;
int Next[N<<1],to[N<<1],head[N],cnt;
int max(int x,int y){return x>y?x:y;}
void add(int u,int v,int eid)
{
to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;
}
int n,dis[N],dp[N],s[N],tot0,ans=0x7fffffff;
void dfs1(int now,int fa)
{
int mx1=0,mx2=0,child=0;
for(int i=head[now];i;i=Next[i])
{
int v=to[i];
if(v==fa) continue;
child++;
dfs1(v,now);
dp[now]=max(dp[v],dp[now]);
dis[now]=max(dis[now],dis[v]+1);
if(mx1<=dis[v]) mx2=mx1,mx1=dis[v];
else if(mx2<dis[v]) mx2=dis[v];
}
if(child>1) dp[now]=max(dp[now],mx1+mx2+2);
else dp[now]=max(dp[now],mx1+mx2+child);
}
void dfs2(int now,int fa,int len1,int len2,int num)
{
int mi=max(max(dp[now],len1),(dp[now]+1)/2+(len1+1)/2+1),child=0;
if(mi<ans) tot0=0,s[++tot0]=num,ans=mi;
else if(mi==ans) s[++tot0]=num;
int max1=0,dmax1=0,fmax1=0,max2=0,dmax2=0;
for(int i=head[now];i;i=Next[i])
{
int v=to[i];
if(v==fa) continue;
if(dis[v]>=max1) fmax1=dmax1,dmax1=max1,max1=dis[v];
else if(dis[v]>=dmax1) fmax1=dmax1,dmax1=dis[v];
else if(dis[v]>fmax1) fmax1=dis[v];
if(dp[v]>=max2) dmax2=max2,max2=dp[v];
else if(dp[v]>dmax2) dmax2=dp[v];
++child;
}
for(int i=head[now];i;i=Next[i])
{
int v=to[i];
if(v==fa) continue;
int mxx0,mxx1;
if(max1==dis[v]) mxx0=dmax1,mxx1=fmax1;
else if(dmax1==dis[v]) mxx0=max1,mxx1=fmax1;
else mxx0=max1,mxx1=dmax1;//儿子链的最大值
int mxx2=(max2==dp[v]?dmax2:max2);//其他儿子的直径
int lenp=max((len2+(mxx0+1)*(child>1)),(mxx0+mxx1+2)*(child>2));//三条链的最值
int le1=max(len1,max(mxx2,lenp)),le2=max(len2+1,(mxx0+2)*(child>1));
dfs2(v,now,le1,le2,i+1>>1);
}
}
struct edge
{
int u,v;
}e[N];
int s0[2][N],mxlen,ll,rr,pre[N];
void dfs3(int now,int fa,int len)
{
if(len>mxlen) mxlen=len,ll=now;
for(int i=head[now];i;i=Next[i])
{
int v=to[i];
if(v==fa||(i+1>>1)==s[1]) continue;
dfs3(v,now,len+1);
}
}
void dfs4(int now,int fa,int len)
{
if(len>mxlen) mxlen=len,rr=now;
for(int i=head[now];i;i=Next[i])
{
int v=to[i];
if(v==fa||(i+1>>1)==s[1]) continue;
pre[v]=now;
dfs4(v,now,len+1);
}
}
void getd(int st,int ty)
{
mxlen=0;
dfs3(st,0,1);
mxlen=0;
dfs4(ll,0,1);
int now=rr;
while(now) s0[ty][++s0[ty][0]]=now,now=pre[now];
}
void work3()
{
int lu=e[s[1]].u,lv=e[s[1]].v;
getd(lu,0),getd(lv,1);
int u=s0[0][s0[0][0]+1>>1],v=s0[1][s0[1][0]+1>>1];
printf("%d %d %d %d\n",lu,lv,u,v);
}
int main()
{
scanf("%d",&n);
for(int u,v,i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
e[i]={u,v};
add(u,v,i),add(v,u,i);
}
dfs1(1,0);
dfs2(1,0,0,0,0);
printf("%d\n",ans);
std::sort(s+1,s+1+tot0);
printf("%d ",tot0);
for(int i=1;i<=tot0;i++) printf("%d ",s[i]);
printf("\n");
work3();
return 0;
}
2018.10.2