C0253 【0617 C组】模拟测试
军训归来的第一场模拟赛，小寄。
C 【0601 C组】树
好神奇的题目。
直径这个东西没什么能入手的性质，我们先考虑进行一些转化。
对于直径，我们去找它的中心点。中心点可能在边上，于是把边拆开，比如边 \((u,v)\) 拆成 \((u,x)(x,v)\)，这样就有了 \(2n-1\) 个点，且直径的中心点都在点上。于是可以进一步把问题变成每次使一条边 \(+2\)，使直径的一半（即半径，就是以中心点为端点延伸的最长路径）最小。至于为什么有半径就一定能找到对应直径的问题，我们下面会讲。
枚举中心点 \(i\)，设离它最远的点距离为 \(r_i\)，显然这样的点一定是叶子。定义所有叶子到 \(i\) 的距离之和为 \(s_i\)，整棵树的叶子数为 \(c\)，这些东西和 \(r_i\) 都可以换根 \(O(n)\)。
那么我们要把以 \(i\) 为中心点的半径控制在 \(r_i\) 最多可以操作 \(\dfrac{c\cdot r_i-s_i}{2}\) 次，如果半径为 \(r_i+2x\) 最多可以操作 \(\dfrac{c\cdot r_i-s_i}{2}+c\cdot x\) 次。因为叶子不可能作为中心点，所以 \(c\) 是定值。记
\(\dfrac{c\cdot r_i-s_i}{2}\) 为 \(o_i\)，小推一下可以得到 \(x=\left\lceil\dfrac{k-o_i}{c}\right\rceil\)，那么 \(i\) 点的答案就是：
\(ans_i=\begin{cases}r_i&k\le o_i\\r_i+2\left\lceil\dfrac{k-o_i}{c}\right\rceil&k>o_i\end{cases}\)
解释一下为啥有半径就一定能找到对应直径。因为我们是直接粗暴地认为直径长为半径两倍，如果你的另一半不足 \(r_i\)，首先根据定义它不是中心点；其次，因为中心点一定在点上，所以在枚举其他点的时候我们会得到正确的答案，故 \(2r_i\) 这个东西是不优的，不会对答案造成影响。
再解释一下为什么 \(o_i\) 是整数。叶子节点都是原来就有的，所以它们到 \(i\) 的距离的奇偶性相同。
现在问题转化成每次给你 \(k\)，求在上述柿子中能得到的最小值。把柿子和询问离线下来，分别按照 \(o_i\) 和 \(k\) 从小到大排序。枚举 \(k\)，那么就是有一段前缀柿子取到第二类而另一段后缀取第一类。分界点可以双指针。后缀那坨可以直接取最小值，前面的可以把上取整转化成根据余数分一下类，然后丢到线段树上。时间复杂度 \(O(n\log n)\)
有一个细节：从 \(u\) 换根到 \(v\) 的时候可能会出现 \(u\) 就是叶子。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define mk make_pair
using namespace std;
typedef pair<int,int>pii;
const int inf=1e18;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
struct edge{
int v,nxt;
}e[800005];
int head[400005],tot,deg[400005];
void add(int u,int v){
e[++tot]=(edge){v,head[u]},head[u]=tot;deg[v]++;
}
int d[400005],cnt[400005],tag[400005],in[400005];
void dfs1(int u,int fa){
cnt[u]=tag[u],in[u]=(tag[u]?0:-inf);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;if(v==fa)continue;
d[v]=d[u]+1;dfs1(v,u);
cnt[u]+=cnt[v],in[u]=max(in[u],in[v]+1);
}
}
int out[400005],s[400005],r[400005],o[400005];
void dfs2(int u,int fa){
vector<pii>vec;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;if(v==fa)continue;
s[v]=s[u]-cnt[v]+(cnt[1]-cnt[v]);
vec.push_back(mk(in[v],v));
out[v]=out[u]+1;
if(tag[u])out[v]=max(out[v],1ll);
}
int pre=-inf;
for(int i=0;i<(int)vec.size();i++){
out[vec[i].se]=max(out[vec[i].se],pre+2);
pre=max(pre,vec[i].fi);
}
int suf=-inf;
for(int i=(int)vec.size()-1;i>=0;i--){
out[vec[i].se]=max(out[vec[i].se],suf+2);
suf=max(suf,vec[i].fi);
}
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;if(v==fa)continue;
dfs2(v,u);
}
}
struct segtree{
#define ls p<<1
#define rs p<<1|1
#define lson l,mid,ls
#define rson mid+1,r,rs
struct Node{
int mi;
}c[1600005];
void pushup(int p){
c[p].mi=min(c[ls].mi,c[rs].mi);
}
void build(int l,int r,int p){
if(l==r){c[p].mi=inf;return;}
int mid=(l+r)>>1;
build(lson),build(rson);
pushup(p);
}
void update(int l,int r,int p,int x,int k){
if(l==r){c[p].mi=min(c[p].mi,k);return;}
int mid=(l+r)>>1;
if(x<=mid)update(lson,x,k);
else update(rson,x,k);
pushup(p);
}
int query(int l,int r,int p,int L,int R){
if(L>R)return inf;
if(L<=l&&r<=R)return c[p].mi;
int mid=(l+r)>>1,res=inf;
if(L<=mid)res=min(res,query(lson,L,R));
if(R>mid)res=min(res,query(rson,L,R));
return res;
}
#undef ls
#undef rs
#undef lson
#undef rson
}Tr;
struct Dec{
int o,id;
}p[400005];
int cmpD(Dec x,Dec y){
return x.o<y.o;
}
int suf[400005];
struct Que{
int k,id;
}q[200005];
int cmpQ(Que x,Que y){
return x.k<y.k;
}
int A[400005],B[400005],ans[200005];
void solve(){
int n=read();
for(int i=1,u,v;i<n;i++){
u=read(),v=read();
add(u,n+i),add(n+i,u);
add(v,n+i),add(n+i,v);
}
int m=2*n-1,Q=read(),c=0;
for(int i=1;i<=m;i++){
if(deg[i]==1)c++,tag[i]=1;
}
dfs1(1,0);
for(int i=1;i<=m;i++){
if(tag[i])s[1]+=d[i];
}
out[1]=-inf;
dfs2(1,0);
int num=0;
for(int i=1;i<=m;i++){
r[i]=max(in[i],out[i]);
o[i]=(r[i]*c-s[i])/2;
A[i]=o[i]/c,B[i]=o[i]%c;
if(!tag[i])p[++num]=(Dec){o[i],i};
}
sort(p+1,p+num+1,cmpD);
suf[num+1]=inf;
for(int i=num;i>=1;i--){
suf[i]=min(suf[i+1],r[p[i].id]);
}
for(int i=1;i<=Q;i++){
q[i].k=read(),q[i].id=i;
}
sort(q+1,q+Q+1,cmpQ);
Tr.build(0,c-1,1);
for(int i=1,j=1;i<=Q;i++){
while(j<=num&&p[j].o<=q[i].k){
Tr.update(0,c-1,1,B[p[j].id],-2*A[p[j].id]+r[p[j].id]);
j++;
}
int res=inf;
res=min(res,suf[j]);
res=min(res,(q[i].k/c)*2+Tr.query(0,c-1,1,0,q[i].k%c-1)+2);
res=min(res,(q[i].k/c)*2+Tr.query(0,c-1,1,q[i].k%c,c-1));
ans[q[i].id]=res;
}
for(int i=1;i<=Q;i++){
printf("%lld\n",ans[i]);
}
}
signed main(){
int T=1;
while(T--)solve();
return 0;
}