题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=N*2,mod=998244353;
#define uLL unsigned long long
#define int long long
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// using kth_set = __gnu_pbds::tree<pair<int, int>, null_type, greater<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>;
using i128=__int128;
const long long inf=1e18;
const long long INF=1e18;
typedef pair<int,int> PII;
typedef long long LL;
using node=tuple<int,int,int>;
int n,m,k;
int h[N], e[M], ne[M],w[M],idx;
int  dep[N],f[N],siz[N],son[N];
int bs;
int dfn[N],top[N],a[N];
int tp,ans;
int st[N],fa[N];
vector<int> g[N];
int mn[N];
void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs1(int x){
    siz[x]=1;
    if(x==1) mn[x]=inf;
    for(int i=h[x];~i;i=ne[i]){
        int v=e[i];
        if(v==fa[x]) continue;
        fa[v]=x;
        mn[v]=min(mn[x],w[i]);
        dep[v]=dep[x]+1;
        dfs1(v);
        siz[x]+=siz[v];
        if(siz[son[x]]<siz[v]) son[x]=v;
    }
  //  cout<<x<<" "<<mn[x]<<"\n";
}
void dfs2(int x){
    dfn[x]=++bs;
    if(son[x]){
        top[son[x]]=top[x];
        dfs2(son[x]);
        for(int i=h[x];~i;i=ne[i]){
            int v=e[i];
            if(v!=fa[x]&&v!=son[x])
            dfs2(top[v]=v);
        }
    }
}
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;
}
void ins(int x){
    if(tp==0){
        st[tp=1]=1;
        return ;
    }
    int ance=lca(st[tp],x);
    while(tp>1&&dep[ance]<dep[st[tp-1]]){
        g[st[tp-1]].push_back(st[tp]);
        tp--;
    }
    if(dep[ance]<dep[st[tp]]) g[ance].push_back(st[tp--]);
    if((!tp)||(st[tp]!=ance)) st[++tp]=ance;
    st[++tp]=x;
}

int dfs3(int x){
    if(siz[x]){
        return mn[x];
    }
    int sum=0;
    for(auto&v:g[x]){
        sum+=dfs3(v);
    }
    siz[x]=0;
    g[x].clear();
    return min(mn[x],sum);
}
void solve()
{
    memset(h, -1, sizeof h);
    bs=0;
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y,z;cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    bs=0;
    dfs1(dep[1]=1);
    dfs2(top[1]=1);
    bs=0;
    memset(siz,0,sizeof(siz));

    int q;cin>>q;
    while(q--){
        int x=1;
        cin>>m;
        for(int i=1;i<=m;i++){
            cin>>a[i];
            siz[a[i]]=1;
        }

        //ans=0,mx=-inf;mn=inf;
        sort(a+1,a+1+m,[&](const auto&p,const auto&q){
            return dfn[p]<dfn[q];
        });
       // cout<<a[1]<<" "<<a[2]<<"\n";
        if(a[1]!=1) st[tp=1]=1;
        for(int i=1;i<=m;i++) ins(a[i]);
        if(tp) while(--tp) g[st[tp]].push_back(st[tp+1]);
        cout<<dfs3(1)<<"\n";
        siz[1]=bs=0;
        g[1].clear();
        for(int i=1;i<=m;i++)
        siz[a[i]]=0,g[a[i]].clear();


        //return ;
    }
}   

signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
   // init();
 //  freopen("in.txt","r",stdin); 
    //freopen("out.txt","w",stdout);
    //cin>>t;
    while(t--) solve();
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla