蒟蒻求助虚树板子
查看原帖
蒟蒻求助虚树板子
455490
Sharpsmile楼主2022/7/10 10:52

RT,只有2 10 两个点是对的。

其他的点看起来是偏大的样子。

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <istream>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <string.h>
#include <map>
#include <unordered_map>
#include <sstream>
#define mp(a,b) make_pair(a,b)
#define int long long
#define p1(x) x.first
#define p2(x) x.second
using namespace std;
int n,q,k;
const int INF=1e15;
vector<pair<int,int>>g[300300],exg[300300];
int dp[300300];
int dfn[300300];
int dep[300300];
int fa[300300][23];
int mn[300300][23];
int ti=0;
bool p[300300];
inline void dfs(int u){
    
    dfn[u]=++ti;
    dep[u]=dep[fa[u][0]]+1;
    for(int i=1;i<=20;i++)
        fa[u][i]=fa[fa[u][i-1]][i-1],
        mn[u][i]=min(mn[u][i-1],mn[fa[u][i-1]][i-1]);
    for(pair<int,int>e:g[u])
        if(p1(e)!=fa[u][0]){
            fa[p1(e)][0]=u;
            mn[p1(e)][0]=p2(e);
            dfs(p1(e));
        }
}
inline int LCA(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    int l=20;
    while(dep[u]>dep[v]){
        if(dep[fa[u][l]]>=dep[v])
            u=fa[u][l];
        l--;
    }
    if(u==v) return u;
    l=20;
    while(l>=0){
        if(fa[u][l]!=fa[v][l])
            u=fa[u][l],v=fa[v][l];
        l--;
    }
    return fa[u][0];
}inline int LMN(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    int l=20;
    int res=INF;
    while(dep[u]>dep[v]){
        if(dep[fa[u][l]]>=dep[v])
            res=min(res,mn[u][l]),u=fa[u][l];
        l--;
    }
    if(u==v) return res;
    l=20;
    while(l>=0){
        if(fa[u][l]!=fa[v][l])
            res=min(res,min(mn[u][l],mn[v][l])),u=fa[u][l],v=fa[v][l];
        l--;
    }
    return min(res,min(mn[u][0],mn[v][0]));
    
}
inline bool cmp(int u,int v){
    return dfn[u]<dfn[v];
}
inline void bd(vector<int>D){
    sort(D.begin(),D.end(),cmp);
    stack<int>s;
    s.push(1);
    for(int u:D){
        int LC=LCA(u,s.top());
        int v=s.top();
            s.pop();
            while(!s.empty()&&dfn[LC]<dfn[v]){
                exg[s.top()].push_back(mp(v,LMN(v,s.top())));
                v=s.top();
                s.pop();
            }
            s.push(v);
        if(dfn[LC]>dfn[v])s.push(LC);
        s.push(u);
    }
    while(s.size()>=2){
        int x=s.top();
        s.pop();
        exg[s.top()].push_back(mp(x,LMN(x,s.top())));
    }
}
inline void calc(int u){
    dp[u]=0;
    for(auto e:exg[u]){
        calc(p1(e));
        if(p[p1(e)])dp[u]+=p2(e);
        else dp[u]+=min(p2(e),dp[p1(e)]);
    }
    exg[u].clear();
}
signed main(){
    ios::sync_with_stdio(false);
    //freopen("/Users/noip2019/Downloads/P7735_2.in","r",stdin);
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back(mp(v,w));
        g[v].push_back(mp(u,w));
    }
    memset(mn,0x3f,sizeof(mn));
    
    dfs(1);
    
    cin>>q;
    while(q--){
        cin>>k;
        vector<int>D;
        for(int i=1;i<=k;i++){
            int x;
            cin>>x;
            D.push_back(x);
            p[x]=1;
        }
        bd(D);
        calc(1);
        cout<<dp[1]<<endl;
        for(int x:D)
            p[x]=0;
    }
    return 0;
}



2022/7/10 10:52
加载中...