求助TLE80分
查看原帖
求助TLE80分
151647
sycqwq楼主2022/4/7 16:40

rt

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e6+5;
struct node
{
    int u,v,nxt;    
}e[maxn];
int n,tot,head[maxn],de[maxn],dfn[maxn],f[maxn][25],cnt;
vector<int> g[maxn];
void add(int x,int y)
{
    e[++tot].v=y;
    e[tot].u=x;
    e[tot].nxt=head[x];
    head[x]=tot;
}
void dfs(int x,int fa)
{
    dfn[x]=++cnt;
    de[x]=de[fa]+1;
    f[x][0]=fa;
    for(int i=1;i<=20;i++)
        f[x][i]=f[f[x][i-1]][i-1];
    for(int i=head[x];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v!=fa)
            dfs(v,x);
    }
}
int lca(int x,int y)
{
    if(de[x]<de[y])
        swap(x,y);
    for(int i=20;i>=0;i--)
        if(de[f[x][i]]>=de[y])
            x=f[x][i];
    if(x==y)
        return x;
    for(int i=20;i>=0;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}
int dis(int x,int y)
{
    return de[y]-de[x];
}
int b[maxn],q,k;
int cmp(int x,int y)
{
    return dfn[x]<dfn[y];
}
int top,stk[maxn];
void build()
{
    sort(b+1,b+k+1,cmp); 
    stk[top=1]=1;
    for(int i=1;i<=k;i++)
    { 
        // cout<<b[i]<<' ';
        int l=lca(stk[top],b[i]);
        // cout<<l<<endl;
        if(b[i]==1)
            continue;
        // if(l==1&&top==1)
        // {
        //     stk[++top]=b[i];
        //     continue;
        // }
        // cout<<"QWQ"<<l<<endl;
        if(l==stk[top])
        {
            stk[++top]=b[i];
            // cout<<"FUCK"<<endl;
        }
        else
        {
            while(top>1&&de[stk[top-1]]>de[l])
                g[stk[top-1]].push_back(stk[top]),--top;
            if(stk[top-1]==l)
                g[l].push_back(stk[top]),--top;
            else
                g[l].push_back(stk[top]),stk[top]=l;
            // cout<<"QWQ"<<endl;
            stk[++top]=b[i];
        }
    }
    // cout<<"QWQ"<<top<<' '<<stk[1]<<endl;
    for(int i=1;i<top;i++)
        g[stk[i]].push_back(stk[i+1]);
}
int dp[maxn][3],bk[maxn],mas,mis,s;//0:和 1:最大值 2:最小值
void solve(int x)
{
    // cout<<"QWQ"<<x<<endl;
    dp[x][2]=INT_MAX;
    dp[x][1]=0;
    dp[x][0]=0;
    int ma=0,mi=INT_MAX,cmi=INT_MAX,cm=0,tp=0;
    if(bk[x])
        tp=1,dp[x][2]=0;
    for(auto v:g[x])
    {
        // cout<<"###"<<x<<' '<<v<<endl;
        solve(v);
        // cout<<bk[v]<<endl;
       s+=1ll*(k-bk[v])*bk[v]*dis(x,v) ;
        // cout<<"###"<<x<<' '<<v<<' '<<bk[v]<<' '<<dis(x,v)<<endl;
        if(bk[x])
        {
            mas=max(mas,dp[x][1]+dis(x,v)+dp[v][1]);
            mis=min(mis,dp[x][2]+dis(x,v)+dp[v][2]);
        }
        bk[x]+=bk[v];
        dp[x][1]=max(dp[x][1],dp[v][1]+dis(x,v));
        dp[x][2]=min(dp[x][2],dp[v][2]+dis(x,v));
        // if(bk[v]&&dp[v][1]+dis(x,v)>ma)
        //     cm=max(cm,ma),ma=dp[v][1]+dis(x,v);
        // else if(bk[v]&&bk[v]!=0)
        //     cm=max(cm,dp[v][1]+dis(x,v));
        // if(bk[v]!=0&&dp[v][2]+dis(x,v)<mi)
        //     cmi=min(cmi,mi),mi=dp[v][2]+dis(x,v);
        // else if(bk[v]!=0)
        //     cmi=min(cmi,dp[v][2]+dis(x,v));
    }
    // cout<<"###"<<ma<<' '<<cm<<endl;
    // cout<<x<<' '<<dp[x][0]<<endl;
    // cout<<"###"<<x<<' '<<mi<<' '<<cmi<<endl;
    // if(tp)
    // {
    //     for(auto v:g[x])
    //         mis=min(mis,dp[v][2]+dis(v,x));
    //     mas=max(mas,ma+cm);
    // }
    // else
    // {
    //     mis=min(mis,mi+cmi);
    //     mas=max(mas,ma+cm);
    // }
    // s+=dp[x][0];

    g[x].clear();
}
int read(){
    int s=0,f=0;
    char ch=getchar();
    while(!isdigit(ch)){
        f|=ch=='-';
        ch=getchar();
    }
    while(isdigit(ch)){
        s=(s<<1)+(s<<3)+(ch^48);
        ch=getchar();
    }
    return f?-s:s;
}
signed main()
{
    // freopen("P4103-1.txt","r",stdin);
    // freopen("P4103.out","w",stdout);
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int a=read(),b=read();
        // cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs(1,1);
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        memset(bk,0,sizeof bk);
        // cin>>k;
        k=read();
        for(int j=1;j<=k;j++)
        {
            b[j]=read();
            // cin>>b[j];
            bk[b[j]]=1;
        }
        build();
        s=0;
        mas=0;
        mis=INT_MAX;
        solve(1);
        printf("%lld %lld %lld\n",s,mis,mas);
    }
    return 0;
}
/*
10 
2 1 
3 2 
4 1 
5 2 
6 4 
7 5 
8 6 
9 7 
10 9 
5 
2 
5 4 
2
10 4 
2 
5 2 
2
6 1 
2 
6 1
*/
2022/4/7 16:40
加载中...