P1399 [NOI2013] 快餐店 (题解)

________a____ · 2021-11-19 17:09:18 · 题解

题目大意

求基环树的直径。

解析

一颗基环树的直径有两种情况：

直径为环上某一点子树的直径。
直径为环上某一点子节点经过环到达另一点子节点。

对于情况 1，显然断环上哪条边对子树直径不会有影响，可以直接处理出来。

对于情况 2，可以求断掉环上任意一边的直径的最大值(也就相当于钦定一条边不属于直径，求出所以可能的直径情况)：

将环上任意一边断开拆环为链，并复制一遍接在末尾：

用一个长度为环的点数的窗口从左向右扫过去，每次更新答案，就可以包含所以断边的情况。

如图，若先断开 1,3 之间的边。

令 dep_i 为 i 点子节点的最大深度，sum_i 为 i 距 1 号节点的距离。

令 a_i=dep_i-sum_i,b_i=dep_i+sum_i。

如图，红色段为 a，蓝色段为 b，紫色段为合并后的直径。

直径长度为 \max\{dep_i+dep_j+sum_j-sum_i\} (sum_i<sum_j)。

也就是直径为 \max\{a_i+b_j\}。

所以可以取 \max\{a_i\}+\max\{b_j\} 为直径。

但可能会出现 i=j 的情况。

所以要维护 a_i 和 b_i 的最大值和次大值。

最后将情况 1 与情况 2 取最大值。

实现

建立一个可以支持单点修改并查询最值的数据结构(如线段树)。

断开环上任意一边并将链复制一遍接在末尾。

若环长为k。

依次扫描每个点，每次更新 a_i,b_i ,前 (k-1) 个点不更新 ans(还没形成一颗完整的树),之后每次查询 a_i 和 b_i 的最大值和次大值更新 ans。

每次更新的信息的有效期为 k 次移动窗口。

而 k 次移动窗口是一个循环，又回到了同一点，直接更新 a 和 b ，替代过期信息即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 200010
#define ls p<<1
#define rs p<<1|1
int n;
vector<int> ver[MAXN],e[MAXN];
inline int read(){
    int a=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') {
        a=(a<<1)+(a<<3)+(ch^48);
        ch=getchar();
    }
    return a;
}
inline void add(int u,int v,int w){
    ver[u].push_back(v);
    e[u].push_back(w);
}
int pre[MAXN];
int w[MAXN];
char mark[MAXN];
int dep[MAXN];
int _ans=0;
void dfs_(int u){ //标记环上的点
    if(mark[u]) return ;
    mark[u]=1;
    dfs_(pre[u]);
}
bool dfs(int u,int fa){ //找环
    for(int v,i=0;i<ver[u].size();i++){
        if((v=ver[u][i])==fa) continue;
        if(pre[v]){
            pre[v]=u;
            w[v]=e[u][i];
            dfs_(u);
            return 1;
        }
        pre[v]=u;
        w[v]=e[u][i];
        if(dfs(v,u)) return 1;
    }
    return 0;
}
void dfs_dep(int u,int fa){ //处理子树直径和dep[u]
    for(int i=0,v;i<ver[u].size();i++){
        if((v=ver[u][i])==fa) continue;
        if(mark[v]) continue;
        dfs_dep(v,u);
        _ans=max(_ans,dep[u]+dep[v]+e[u][i]);
        dep[u]=max(dep[u],dep[v]+e[u][i]);
    }
}
int a[MAXN],b[MAXN];
inline bool cmp1(int _a,int _b){ //因为是记录的点的编号,所以按数组对应元素排序
    return a[_a]<a[_b];
}
inline bool cmp2(int _a,int _b){
    return b[_a]<b[_b];
}
struct node {
    int a,aa,b,bb;
    node operator + (node _b){
        node res; //奇丑无比的区间最大值次大值维护
        vector<int> rec;
        rec.push_back(a);
        rec.push_back(aa);
        rec.push_back(_b.a);
        rec.push_back(_b.aa);
        sort(rec.begin(),rec.end(),cmp1);
        res.a=rec[3],res.aa=rec[2];
        rec.clear();
        rec.push_back(b);
        rec.push_back(bb);
        rec.push_back(_b.b);
        rec.push_back(_b.bb);
        sort(rec.begin(),rec.end(),cmp2);
        res.b=rec[3],res.bb=rec[2];

        return res;
    }
}data[MAXN<<2];
inline void push_up(int p){
    data[p]=data[ls]+data[rs];
}
inline void build(int l,int r,int p){
    if(l==r){
        data[p].a=data[p].b=l;
        //记录对应节点编号
        return ;
    }
    int mid=l+r>>1;
    build(l,mid,ls);
    build(mid+1,r,rs);
    push_up(p);
}
void upd(int l,int r,int x,int p){
    if(l==r){
        // 确实什么都没有
        return ;
    }
    int mid=l+r>>1;
    if(mid>=x) upd(l,mid,x,ls);
    else upd(mid+1,r,x,rs);
    push_up(p);
}
inline int qu(){
    if(data[1].a==data[1].b) //如果是同一点，分类讨论更新
        return max(a[data[1].a]+b[data[1].bb],a[data[1].aa]+b[data[1].b]);
    return a[data[1].a]+b[data[1].b]; //不是同一点，直接更新
}
signed main(){
    scanf("%lld",&n);
    for(int i=1,u,v,w;i<=n;i++){
        u=read();
        v=read();
        w=read();
        add(u,v,w);
        add(v,u,w);
    }
    dfs(1,0);
    int __s=-1,sum=0,ans=LONG_LONG_MAX;
    for(int i=1;i<=n;i++)
        if(mark[i]) {
            __s=i;//随便选一个开始点
            dfs_dep(i,0);
        }
    memset(a,0xcf,sizeof a); //初始-inf
    memset(b,0xcf,sizeof b);
    for(int i=__s;mark[i]<=2;i=pre[i]){ //如果第3次扫到一个节点代表已经处理完了
        mark[i]++;
        if(mark[pre[i]]<2){
            a[i]=dep[i]-sum;
            b[i]=dep[i]+sum;
            //upd(1,n,i,1);
            sum+=w[i];
            if(mark[pre[pre[i]]]==2) //因为没有查询，最后建树时一次性push_up会更快
                build(1,n,1);
            continue;
        }
        a[i]=dep[i]-sum;
        b[i]=dep[i]+sum;
        sum+=w[i];
        upd(1,n,i,1);//单点修改
        ans=min(ans,qu());
    }
    if(ans<_ans) ans=_ans; //如果子树直径更长久选子树直径
    printf("%.1lf",ans*1.0/2);//答案要除以2输出
    return 0;
}