树题解

闲扯

~~好巧不巧今天 B 组 C 题也叫树。~~

军训回来复健力。

传送门

题解

由于直径没有什么好的性质，我们考虑把直径拆成两段长度相等的半径处理。

又由于直径的中点可能在某条边上，我们在每条边上加一个点，比如原先 $(u,v)$ 间有一条边，我们在其中加一个点 $e$ 变成 $(u,e),(e,v)$ 两条边。这样直径的中点就一定在一个点上了。

但这样计算直径就要除以二（半径），为防止出错我们将每次边权 $+1$ 变成 $+2$，这样就不会有问题了。

考虑把所有边权都加在叶子结点到父亲的边上，容易发现这样肯定是不劣的。

我们可以先做一遍树形 DP，求出每个非叶结点到叶子结点的最远距离 $r_i$，每个非叶节点到叶子结点的距离和 $s_i$，另外还要统计叶子结点的个数 $c$。需要注意，为方便 DP，这里默认根节点度数不为 $1$，如果是 $1$ 就换一个。

然后如何维护我们没看懂题解，@李至擎给我们讲了他的做法。

考虑假如确定中心点后，一个 $K$ 要加到树上有几种情况。

能把半径补齐，且能使得所有叶子结点到该结点的距离小于等于半径，此时 $K \le \frac{r_i \times c - s_i}{2}$，直径长度为 $r_i$（注意相对于原图是乘以二的）。
根本不够把另外一条边补得和半径一样长，容易发现这种情况必然存在另一个中心点满足情况 $1$，直接不考虑。
能补齐的情况下还多，此时最优策略显然是把多的平均分给叶子结点，假如这种情况下直径等于 $r_i+2x$，那么 $\frac{r_i \times c - s_i}{2} < K \le\frac{r_i \times c - s_i}{2}+x\times c$

为方便叙述，我们设 $ O_i=\frac{r_i \times c - s_i}{2}$。

容易发现情况 $1$ 的答案和 $K$ 无关，且按 $O_i$ 排序后恰好是一个后缀，直接维护一个后缀最小值即可。

对于情况 $3$，我们化一下式子发现 $x=\left\lceil\frac{k-O_i}{c}\right\rceil$，则答案为 $2\left\lceil\frac{k-O_i}{c}\right\rceil+r_i$

考虑进行一些化简降低耦合度，首先容易想到将上取整转化为分类讨论，即：

$$ \begin{cases} 2\left\lfloor\frac{k}{c}\right\rfloor + 2 - 2\left\lfloor\frac{O_i}{c}\right\rfloor + r_i & k\bmod c>O_i \bmod c \\ 2\left\lfloor\frac{k}{c}\right\rfloor-2\left\lfloor\frac{O_i}{c}\right\rfloor+r_i & k\bmod c\le O_i \bmod c \end{cases} $$

容易想到先把 $K$ 和 $O_i$ 离线下来从小到大排序，每次碰到 $K$ 维护一个指针把小于等于它的 $O_i$ 对应的 $- 2\left\lfloor\frac{O_i}{c}\right\rfloor+r_i$ 的全部加进一棵按 $O_i \bmod c$ 维护线段树里，然后查询前缀、后缀最小值还有情况一的后缀最小值分别代式子就完事了。

有一堆细节要处理，具体看代码。

code

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
using namespace std;
using i64=long long;
#define gc getchar()
inline i64 read(){
    i64 x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const i64 N=4e5+5,inf=1e18;
i64 n,q,cnte,lf;
vector<i64> e[N];
struct Node{
    i64 mx,se;
    Node():mx(-inf),se(-inf){};
    void operator()(const i64 &r){
        if(r>=mx){
            se=mx;mx=r;
        }else if(r>se){
            se=r;
        }
    }
};
Node dp[N],pd[N];
i64 pd1[N],sum[N],sz[N],rt=1;
void dfs(i64 x,i64 fa){
    sum[x]=0;
    for(auto i:e[x]){
        if(i==fa) continue;
        dfs(i,x);
        sum[x]+=sum[i]+sz[i];
        sz[x]+=sz[i];
        dp[x](dp[i].mx+1);
    }
    if(e[x].size()==1){
        sz[x]=1;
        dp[x](0);
    }
}
void dfs1(i64 x,i64 fa){
    for(auto i:e[x]){
        if(i==fa) continue;
        pd[i](dp[i].mx);
        pd[i](dp[i].se);
        if(pd[x].mx==dp[i].mx+1){
            pd[i](pd[x].se+1);
        }else{
            pd[i](pd[x].mx+1);
        }
        pd1[i]=pd1[x]+sz[rt]-sz[i]*2;
        dfs1(i,x);
    }
}
i64 o[N];
struct SegmentTree{
    #define mid ((l+r)>>1)
    #define lson l,mid,id<<1
    #define rson mid+1,r,id<<1|1
    i64 querymin[N<<1];
    void clear(){
        mem(querymin,0x3f);
    }
    void PushUp(i64 id){
        querymin[id]=min(querymin[id<<1],querymin[id<<1|1]);
    }
    void Update(i64 X,i64 P,i64 l=0,i64 r=lf,i64 id=1){
        if(l==r){
            querymin[id]=min(querymin[id],P);
            return;
        }
        if(X<=mid) Update(X,P,lson);
        else       Update(X,P,rson);
        PushUp(id);
    }
    i64 Ask(i64 L,i64 R,i64 l=0,i64 r=lf,i64 id=1){
        if(L<=l&&r<=R){
            return querymin[id];
        }
        i64 res=inf;
        if(L<=mid) res=min(res,Ask(L,R,lson));
        if(mid< R) res=min(res,Ask(L,R,rson));
        return res;
    }
}mt;
struct node{
    i64 op,r;
}nds[N];
bool cmp(node &a,node &b){
    return a.op<b.op;
}
i64 suf[N];
struct ques{
    i64 pos,num;
}qq[N];
i64 ans[N];
bool cmp1(ques &a,ques &b){
    return a.num<b.num;
}
i64 cntn;
signed main(){
    cnte=n=read();
    mt.clear();
    forup(i,1,n-1){
        i64 u=read(),v=read();++cnte;
        e[u].push_back(cnte);e[cnte].push_back(u);
        e[v].push_back(cnte);e[cnte].push_back(v);
    }
    forup(i,1,cnte){
        if(e[i].size()==1){
            lf++;
        }
    }
    forup(i,1,cnte){
        if(e[i].size()>1){
            rt=i;
            break;
        }
    }
    dfs(rt,0);
    pd[rt]=dp[rt];
    pd1[rt]=sum[rt];
    dfs1(rt,0);
    forup(i,1,cnte){
        o[i]=(pd[i].mx*lf-pd1[i])/2;
        if(e[i].size()>1) nds[++cntn]=node{o[i],pd[i].mx};
    }
    sort(nds+1,nds+cntn+1,cmp); 
    suf[cntn+1]=inf;
    fordown(i,cntn,0){
        suf[i]=min(suf[i+1],nds[i].r);
    }
    q=read();
    forup(i,1,q){
        qq[i].num=read();
        qq[i].pos=i;
    }
    sort(qq+1,qq+n+1,cmp1);
    i64 l=1;
    forup(i,1,q){
        while(l<=cntn&&nds[l].op<=qq[i].num){
            mt.Update(nds[l].op%lf,-2*(nds[l].op/lf)+nds[l].r);
            l++;
        }
        i64 res=inf;
        res=min(res,suf[l]);
        res=min(res,2*(qq[i].num/lf)+2+mt.Ask(0,qq[i].num%lf));
        res=min(res,2*(qq[i].num/lf)+mt.Ask(qq[i].num%lf,lf-1));
        ans[qq[i].pos]=res;
    }
    forup(i,1,q){
        printf("%lld\n",ans[i]);
    }
}

树 题解

闲扯

题解

code

Comments

树题解