联盟

Source and Judge

雅礼noip模拟题

问题

给出一棵树,可以断开再连接一条边,求最小直径,n小于300000
要求输出最小直径,和最优方案中所有可能断开的边,然后输出一组断开和连接的具体方案

Record

7h

Analysis

请先思考后再展开

真tm佩服我的耐心
都快忘记最初的思路了……太可怕了
做法繁琐,细节无数,码量巨大,不愧是雅礼的防ak题

果然直径有很多性质,特别好用,虽然不会证明

  1. 就是两棵树合并起来,新的直径端点一定是在原本两边直径端点中产生
  2. 然后最优的连接方案一定是将两边直径的中点连接起来,这个倒好证明一点,连接其他地方一定不会更优
    $L=max(L1,L2,\lceil \frac{L1}{2} \rceil+\lceil \frac{L2}{2} \rceil+1)$

考虑枚举每条边,断开他,然后问题变成求两边的直径,这个在处理了dfs序以后是可以用线段树维护的
(注意,为了确保任何区间都能形成联通块,要回溯,这个在st表用深度求lca时也要用到)
相当于,只用这段区间内的点,形成的树的直径,利用上面说的那个性质1合并(记录具体端点)

理论复杂度nlogn,但实际上因为结构体的维护,常数巨大,需要卡常
本题有线性做法,感觉很繁琐,就没去搞

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
namespace mine
{
const int MAX_N=310000;
const int INF=0x3f3f3f3f;
int myabs(int x) {return x>0?x:-x;}
int hou[MAX_N],dep[MAX_N],faid[MAX_N],ff[MAX_N];//连向父亲的边的编号
struct Edge{int y,g;}e[MAX_N*2];
int ln=0;void ins(int x,int y) {e[++ln]=(Edge){y,hou[x]};hou[x]=ln;}
int d1[MAX_N],d2[MAX_N],id=0;
int h[MAX_N*2][25];
void dfs(int x,int fa)
{
dep[x]=dep[fa]+1;ff[x]=fa;
d1[x]=d2[x]=++id;h[id][0]=x;
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
faid[y]=(k+1)/2;dfs(y,x);
d2[x]=++id;h[id][0]=x;//确保连续的dfs序能联通
}
}
int getmin(int x,int y) {return dep[x]<dep[y]?x:y;}
int bin[40],log[MAX_N*2];
int getlca(int x,int y)
{
x=d1[x];y=d2[y];
if(x>y) swap(x,y);//debug
int lg=log[y-x+1];
return getmin(h[x][lg],h[y-bin[lg]+1][lg]);
}
int dis(int x,int y) {return (x==0 or y==0)?INF:dep[x]+dep[y]-2*dep[getlca(x,y)];}
void preST()
{
bin[0]=1;for(int i=1;i<=30;i++) bin[i]=bin[i-1]<<1;
log[1]=0;for(int i=2;i<MAX_N*2;i++) log[i]=log[i>>1]+1;
dfs(1,0);
for(int i=1;bin[i]<=id;i++)
for(int x=1;x<=id-bin[i]+1;x++)
h[x][i]=getmin(h[x][i-1],h[x+bin[i-1]][i-1]);
}
struct Data{int x,y;};
Data getmax(Data a,Data b) {return dis(a.x,a.y)>dis(b.x,b.y)?a:b;}
Data merg(Data x,Data y)
{
int a=x.x,b=x.y,c=y.x,d=y.y;
if(a==0 and b==0) return y;
if(c==0 and d==0) return x;
Data now=getmax((Data){a,b},(Data){a,c});
now=getmax(now,(Data){a,d});
now=getmax(now,(Data){b,c});
now=getmax(now,(Data){b,d});
return getmax(now,(Data){c,d});
}
Data zj[MAX_N*2*4];
struct SegmentTree
{
#define lc 2*x
#define rc 2*x+1
void build(int x,int l,int r)
{
if(l==r) {zj[x]=(Data){h[l][0],h[l][0]};return;}
int mid=(l+r)>>1;
build(lc,l,mid);build(rc,mid+1,r);
zj[x]=merg(zj[lc],zj[rc]);
}
Data ask(int x,int l,int r,int fl,int fr)
{
if(l==fl and r==fr) return zj[x];
int mid=(l+r)>>1;
if(fr<=mid) return ask(lc,l,mid,fl,fr);
if(fl>mid) return ask(rc,mid+1,r,fl,fr);
return merg(ask(lc,l,mid,fl,mid),ask(rc,mid+1,r,mid+1,fr));
}
}sgt;
vector<int> output;
void main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n-1;i++)
{
int x,y;scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
preST();
sgt.build(1,1,id);
//for(int i=1;i<=n;i++) printf("%d:%d %d fm=%d\n",i,d1[i],d2[i],fm[i]);
//printf("id=%d\n",id);
int some;//one of result
int ans=INF;
for(int x=2;x<=n;x++)//x->fa
{
Data in=sgt.ask(1,1,id,d1[x],d2[x]);
Data out=sgt.ask(1,1,id,1,d1[x]-1);
if(d2[x]+1<=id) out=merg(out,sgt.ask(1,1,id,d2[x]+1,id));
int ln1=dis(in.x,in.y),ln2=dis(out.x,out.y);
int now=max( int(ceil((double)ln1/2)+ceil((double)ln2/2))+1,max(ln1,ln2) );
//printf("x=%d in=%d->%d=%d out=%d->%d=%d now=%d\n",x,in.x,in.y,ln1,out.x,out.y,ln2,now);
if(now<ans)
{
ans=now;output.clear();
output.push_back(faid[x]);some=x;
}
else if(now==ans) output.push_back(faid[x]);
}
sort(output.begin(),output.end());
printf("%d\n%d ",ans,output.size());
for(int i=0;i<(int)output.size();i++) printf("%d ",output[i]);
int x=some;
Data in=sgt.ask(1,1,id,d1[x],d2[x]);
Data out=sgt.ask(1,1,id,1,d1[x]-1);
if(d2[x]+1<=id) out=merg(out,sgt.ask(1,1,id,d2[x]+1,id));
int a,b,ln1=dis(in.x,in.y),ln2=dis(out.x,out.y);
for(int i=d1[x];i<=d2[x];i++)
if(myabs(dis(h[i][0],in.x)-dis(h[i][0],in.y))==(ln1&1) and
dis(h[i][0],in.x)+dis(h[i][0],in.y)==ln1) a=h[i][0];
for(int i=1;i<=d1[x]-1;i++)
if(myabs(dis(h[i][0],out.x)-dis(h[i][0],out.y))==(ln2&1) and
dis(h[i][0],out.x)+dis(h[i][0],out.y)==ln2) b=h[i][0];
for(int i=d2[x]+1;i<=id;i++)
if(myabs(dis(h[i][0],out.x)-dis(h[i][0],out.y))==(ln2&1) and
dis(h[i][0],out.x)+dis(h[i][0],out.y)==ln2) b=h[i][0];
printf("\n%d %d %d %d",x,ff[x],a,b);
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/699c.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%