题目描述

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], 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];
void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs1(int x){
    siz[x]=1;
    for(int i=h[x];~i;i=ne[i]){
        int v=e[i];
        if(v==fa[x]) continue;
        fa[v]=x;
        dep[v]=dep[x]+1;
        dfs1(v);
        siz[x]+=siz[v];
        if(siz[son[x]]<siz[v]) son[x]=v;
    }
}
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 sum[N],mx1[N],mn1[N];
int mx[N],mn[N];
PII s[N];
void dfs3(int x){
    sum[x]=0;
    mx1[x]=-inf;
    mn1[x]=inf;
    mx[x]=-inf;
    mn[x]=inf;
    s[x]={0,0};
    if(siz[x])
    {
        s[x]={1,dep[x]};
        mx1[x]=dep[x];
        mn1[x]=dep[x];
    }
    //cout<<s[x].second<<" "<<x<<"\n";
    for(auto&v:g[x])
    {
        if(v==fa[v]) continue;
        dfs3(v);
        sum[x]+=sum[v];
        sum[x]+=s[x].second*s[v].first+s[v].second*s[x].first-2*s[x].first*s[v].first*dep[x];
        s[x].first+=s[v].first;
        s[x].second+=s[v].second;
        mx[x]=max({mx[x],mx1[x]+mx1[v]-2*dep[x],mx[v]});
        mn[x]=min({mn[x],mn1[x]+mn1[v]-2*dep[x],mn[v]});
        mx1[x]=max(mx1[x],mx1[v]);
        mn1[x]=min(mn1[x],mn1[v]);
    }  

    siz[x]=0;
    g[x].clear();
}
void solve()
{
    memset(h, -1, sizeof h);
    bs=0;
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    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]);
        dfs3(1);
        siz[1]=bs=0;


        cout<<sum[1]<<" "<<mn[1]<<" "<<mx[1]<<"\n";
        //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