题解：P11161 【MX-X6-T7】夏が終わる

ZLCT · 2025-04-04 21:52:12 · 题解

【MX-X6-T7】夏が終わる

不清楚这个题如果要卡 LCT 应该怎么卡，正常 cin/cout 最慢的点才跑了 1.5s。

题目分析

首先一个直觉就是只要每个点不在树上边的度数 \ge 2 就一定能找到一条全是 0 的回路。\ 这点出题人的题解证明已经比较详尽了，这里给出一个简单强势的证明方法：\ 根据奥尔定理，只要一个图对于每对不相邻的顶点 (u,v)，满足 deg_u+deg_v\ge n 则该图一定存在一条哈密顿回路。\ 在这个题中，不能通过 0 边相邻等价于树上有一条边连接 (u,v)。\ 而 deg_u+deg_v\ge n 用树上度数去表达就等价于 (n-1-Deg_u)+(n-1-Deg_v)=2n-2-Deg_u-Deg_v\ge n。\ 也就是 Deg_u+Deg_v\le n-2。\ 我们设树上度数最大的点度数为 D，显然当 D=n-1/n-2 的时候我们不符合条件，并且由于一个哈密顿回路每个点的度数为 2，这也明显构不成哈密顿回路。\ 那当 D<n-2 时，我们只需要另一个点的度数 \le n-2-D 就可以保证有哈密顿回路了。\ 所以当（直径 >5）或（直径 =5 且有至少 2 个非直径中心节点度数 \ge 2 时）一定有哈密顿回路。\ 接下来我们分类讨论：

• 直径 =4。此时一定只存在两个非叶子节点，并且由于一条边连接了这两点，所以它俩至少可以有一个公共节点可以相连，然后你随便将这两个点向其余能连的点连一条边，你会发现其余有用的边全都不在树上，那想构造一个哈密顿回路就易如反掌了。
• 直径 =5 且只有一个非直径中心节点度数 \ge 2。那我们可以先将度数最大的点与其树上不相邻的那个点连边，这样以后将它俩看作一个点继续跑上一个方法就行了。\ 最后你会发现这两种方法的前提是 n\ge 5，一看题面正好，不需要特判了。

那对于 D=n-1/n-2 的情况那就是我们可以转化成要选择其 2/1 条边删除，代价是边权，求最小代价，这是个显然的贪心。只需要选最小的边权即可。

实现

实现方面由于有加/删边且修改操作是针对路径的，所以我们选择 LCT。\ 首先我们通过边权化点权的技巧把边权转化。\ 对于操作 1,2 直接正常 LCT 即可（删边可能需要注意思考一下），我们来看如何维护答案。\ 首先这个题要求子树 \min，由于 \min 没有逆元，所以我们只能开一个 multiset 去存。\ 那对于一条链要通过虚边贡献到其子树，我们需要知道其链首节点的权值，这一点我们可以维护。\ 但是我们在反转子树后发现无法通过原链首节点的权值得到反转后链首节点的权值，那么我们这里利用双向维护法，发现新的链首就是原链尾，我们只需要再维护一下链尾的点权，反转时也调换一下即可。\ 最后统计答案时为了方便，我们还有一个小技巧。\ 若当前答案不为 0，那一定有个重心 T，我们可以通过 split(T,T) 的方式规避掉实链上的讨论。

总结

本题首先结论还是比较好猜的，感性理解起来也比较容易。\ 实现方面我们通过利用：边权转点权，维护子树信息，双向维护法这三种方法也能比较轻松完成代码实现。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+666;
const int inf=5e11+7;
int n,q,deg[N],cnt;
pair<int,int>e[N];
struct node{
    int son[2],fa;
    bool tag;
    int val,tag2,lft,rft,siz;
    multiset<int>si;
}tr[N<<1];
void dfs(int x){
    if(tr[x].son[0])dfs(tr[x].son[0]);
    cout<<x<<" ";
    if(tr[x].son[1])dfs(tr[x].son[1]);
}
bool notroot(int x){
    return tr[tr[x].fa].son[0]==x||tr[tr[x].fa].son[1]==x;
}
void pushup(int x){
    if(!x)return;
    if(tr[x].son[0])tr[x].lft=tr[tr[x].son[0]].lft;
    else tr[x].lft=tr[x].val;
    if(tr[x].son[1])tr[x].rft=tr[tr[x].son[1]].rft;
    else tr[x].rft=tr[x].val;
    tr[x].siz=tr[tr[x].son[0]].siz+tr[tr[x].son[1]].siz+1;
}
void pushdown(int x){
    if(tr[x].tag){
        swap(tr[x].son[1],tr[x].son[0]);
        swap(tr[tr[x].son[0]].lft,tr[tr[x].son[0]].rft);
        swap(tr[tr[x].son[1]].lft,tr[tr[x].son[1]].rft);
        tr[tr[x].son[0]].tag^=1;
        tr[tr[x].son[1]].tag^=1;
        tr[x].tag=0;
    }
    if(tr[x].tag2){
        tr[tr[x].son[0]].tag2+=tr[x].tag2;
        tr[tr[x].son[1]].tag2+=tr[x].tag2;
        tr[tr[x].son[0]].val+=tr[x].tag2;
        tr[tr[x].son[1]].val+=tr[x].tag2;
        tr[tr[x].son[0]].lft+=tr[x].tag2;
        tr[tr[x].son[0]].rft+=tr[x].tag2;
        tr[tr[x].son[1]].lft+=tr[x].tag2;
        tr[tr[x].son[1]].rft+=tr[x].tag2;
        tr[x].tag2=0;
    }
}
void pushall(int x){
    if(notroot(x))pushall(tr[x].fa);
    pushdown(x);
}
void rotate(int x){
    int y=tr[x].fa,z=tr[y].fa;
    int k=tr[y].son[1]==x;
    if(notroot(y)){
        tr[z].son[tr[z].son[1]==y]=x;
    }
    tr[x].fa=z;
    tr[y].son[k]=tr[x].son[k^1];
    tr[tr[x].son[k^1]].fa=y;
    tr[x].son[k^1]=y;
    tr[y].fa=x;
    pushup(y);
    pushup(x);
}
void splay(int x){
    pushall(x);
    while(notroot(x)){
        int y=tr[x].fa,z=tr[y].fa;
        if(notroot(y)){
            rotate((tr[y].son[1]==x)^(tr[z].son[1]==y)?x:y);
        }
        rotate(x);
    }
}
void access(int x){
    for(int y=0;x;x=tr[x].fa){
        splay(x);
        if(y)tr[x].si.erase(tr[x].si.lower_bound(tr[y].lft));
        if(tr[x].son[1])tr[x].si.insert(tr[tr[x].son[1]].lft);
        tr[x].son[1]=y;
        pushup(x);
        y=x;
    }
}
void makeroot(int x){
    access(x);
    splay(x);
    tr[x].tag^=1;
    swap(tr[x].lft,tr[x].rft);
}
void split(int x,int y){
    makeroot(x);
    access(y);
    splay(y);
}
void link(int x,int y){
    makeroot(x);
    makeroot(y);
    tr[x].fa=y;
    tr[y].si.insert(tr[x].lft);
}
void cut(int x,int y){
    makeroot(x);
    access(y);splay(x);
    tr[x].son[1]=0;tr[y].fa=0;
    pushup(x);
}
void Cut(int x){
    int u=e[x].first,v=e[x].second;
    cut(u,x+n);cut(x+n,v);
}
int rt;
signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;++i){
        tr[i].val=inf;
        pushup(i);
    }
    for(int i=1;i<n;++i){
        int u,v,w;cin>>u>>v>>w;
        cnt++;
        e[cnt]={u,v};
        deg[u]++;deg[v]++;
        if(deg[u]==n-2)rt=u;
        if(deg[v]==n-2)rt=v;
        tr[cnt+n].val=w;
        pushup(cnt+n);
        link(u,cnt+n);link(cnt+n,v);
    }
    while(q--){
        int op;cin>>op;
        if(op==1){
            int id,u,v,w;cin>>id>>u>>v>>w;
            Cut(id);
            cnt++;
            e[cnt]={u,v};
            tr[cnt+n].val=w;
            pushup(cnt+n);
            link(u,cnt+n);link(cnt+n,v);
            if(deg[e[id].first]==n-2)rt=0;
            if(deg[e[id].second]==n-2)rt=0;
            deg[e[id].first]--;deg[e[id].second]--;
            deg[u]++;deg[v]++;
            if(deg[u]==n-2)rt=u;
            if(deg[v]==n-2)rt=v;
        }else{
            int u,v,w;cin>>u>>v>>w;
            split(u,v);
            tr[v].val+=w;
            tr[v].tag2+=w;
            tr[v].lft+=w;
            tr[v].rft+=w;
        }
        if(!rt){
            cout<<0<<"\n";
        }else{
            makeroot(rt);access(rt);
            int res=*tr[rt].si.begin();
            if(deg[rt]==n-1){
                res+=*next(tr[rt].si.begin());
            }
            cout<<res<<"\n";
        }
    }
    return 0;
}