【UOJ#61】【UR#5】怎样更有力气 | Mrsrz's blog

暴力

题目大意：

给定一棵树的草图，第 $i$ 天给出 $u_i,v_i,w_i$，你可以任选草图上位于 $u_i$ 与 $v_i$ 之间的两个点并实际修一条路，代价为 $w_i$。

有 $p$ 条限制，第 $i$ 条限制形如 $u_i,v_i,t_i$，表示第 $t_i$ 天，$u_i$ 与 $v_i$ 之间不能修路。

求让 $n$ 个点连通的最小代价。

题解：

题目就是要求最小生成树，所以容易想到按 $w$ 排序以后分别考虑。

对于同一个连通块的点，我们可以将它们放在一起考虑。

我们考虑对一个 $u,v$，将它们所在的所有连通块找出来。然后若两个连通块在这条路径里的点不是两两有边，则将这两个连通块连起来。

由于最多有 $p$ 条限制，枚举两个连通块，但不连边的次数只有 $O(p)$ 次，是合理的。

同一连通块的点不一定在树上连续，而暴力跳树的复杂度无法接受。简单的方法是若一个结点和父亲在同一个连通块，就用并查集并起来。每次暴力往上跳。这样暴力往上跳而没有合并的次数也只有 $O(p)$ 次。

并未仔细证明，感性理解得到的东西

然后枚举两个连通块并考虑连边即可。

Code：

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int N=3e5+5;
typedef long long LL;
LL ans;
int n,m,p,head[N],cnt,nxt[N],dep[N],sz[N],son[N],fa[N],top[N];
vector<pair<int,int> >vc[N];
inline bool cmp(int a,int b){return dep[a]<dep[b];}
struct dsu{
    int fa[N];
    inline int find(int x){while(x!=fa[x])x=fa[x]=fa[fa[x]];return x;}
    inline void merge(int x,int y){x=find(x),y=find(y);if(x>y)swap(x,y);if(x!=y)fa[y]=x;}
    inline void init(){for(int i=1;i<=n;++i)fa[i]=i;}
}A,B;
struct que{
    int u,v,w,t;
    inline bool operator<(const que&rhs)const{return w<rhs.w;}
}d[N];
void dfs(int now){
    sz[now]=1,son[now]=0;
    for(int to=head[now];to;to=nxt[to]){
        dep[to]=dep[now]+1;
        dfs(to);
        sz[now]+=sz[to];
        if(!son[now]||sz[son[now]]<sz[to])son[now]=to;
    }
}
void dfs2(int now){
    if(son[now])top[son[now]]=top[now],dfs2(son[now]);
    for(int to=head[now];to;to=nxt[to])if(to!=son[now])dfs2(top[to]=to);
}
inline int LCA(int x,int y){
    while(top[x]!=top[y])if(dep[top[x]]>dep[top[y]])x=fa[top[x]];else y=fa[top[y]];
    return dep[x]<dep[y]?x:y;
}
bool check(int u,int v,int t,int x){
    if(dep[x]<dep[t])return 0;
    return(LCA(u,x)==x||LCA(v,x)==x);
}
void work(int u,int v,int w,vector<pair<int,int> >&vc){
    static int sz[N],sta[N];
    static bool vis[N];
    static map<int,int>mp[N];
    int top=0;
    int t=LCA(u,v);
    for(int x=u;dep[x]>=dep[t];){
        int tp=B.find(x);
        if(dep[tp]<dep[t])tp=t;
        if(A.find(tp)==A.find(fa[tp]))B.merge(fa[tp],tp);
        int bel=A.find(tp);
        if(!vis[bel]){sta[++top]=bel,vis[bel]=1;}
        sz[bel]+=dep[x]-dep[tp]+1;
        x=fa[tp];
    }
    for(int x=v;dep[x]>=dep[t];){
        int tp=B.find(x);
        if(dep[tp]<dep[t])tp=t;
        if(A.find(tp)==A.find(fa[tp]))B.merge(fa[tp],tp);
        int bel=A.find(tp);
        if(!vis[bel]){sta[++top]=bel,vis[bel]=1;}
        sz[bel]+=dep[x]-dep[tp]+1;
        x=fa[tp];
    }
    --sz[A.find(t)];
    for(auto it:vc){
        int x=it.first,y=it.second;
        if(check(u,v,t,x)&&check(u,v,t,y)){
            int fx=A.find(x),fy=A.find(y);
            if(fx!=fy)++mp[fx][fy],++mp[fy][fx];
        }
    }
    static set<int>st;
    st.clear();
    int dd=0;
    for(int i=1;i<=top;++i)st.insert(sta[i]);
    for(int i=1;i<=top&&st.size();++i){
        static int D[N];int TOP=0;
        for(auto j:st)if(A.find(sta[i])!=A.find(j)&&(LL)sz[sta[i]]*sz[j]>mp[sta[i]][j]){
            D[++TOP]=j;
            ++dd;
            A.merge(sta[i],j);
        }
        for(int i=1;i<=TOP;++i)st.erase(D[i]);
    }
    for(int i=1;i<=top;++i)mp[sta[i]].clear(),sz[sta[i]]=0,vis[sta[i]]=0;
    ans+=(LL)w*dd;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>p;
    for(int i=2;i<=n;++i){
        cin>>fa[i];
        nxt[i]=head[fa[i]],head[fa[i]]=i;
    }
    dfs(dep[1]=1),dfs2(top[1]=1);
    A.init(),B.init();
    for(int i=1;i<=m;++i){
        cin>>d[i].u>>d[i].v>>d[i].w;
        d[i].t=i;
    }
    sort(d+1,d+m+1);
    while(p--){
        int u,v,t;
        cin>>t>>u>>v;
        vc[t].emplace_back(u,v);
    }
    for(int i=1;i<=m;++i)
    work(d[i].u,d[i].v,d[i].w,vc[d[i].t]);
    cout<<ans<<'\n';
    return 0;
}