锰锌刚学虚树莫名MLE求条
查看原帖
锰锌刚学虚树莫名MLE求条
1219462
Ratio_Y楼主2024/8/9 18:02

rt

#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx int
inline lx qr()
{
	char ch=getchar();lx x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
#undef lx
#define qr qr()
const int Ratio=0;
const int N=1e6+5;
int n,m;
int hh[N],to[N<<1],ne[N<<1],cnt;
int dfn[N],dep[N],siz[N],fx[N][21],tot;
int zc[N],zc1[N];
ll mi[N],ma[N],g[N];
ll ans,ansmi,ansma;
bool yz[N];
bool cmp(int x,int y){return dfn[x]<dfn[y];}
namespace Wisadel
{
    void Wadd(int u,int v)
    {
        to[++cnt]=v;
        ne[cnt]=hh[u];
        hh[u]=cnt;
    }
    void Wdfs(int u,int fa)
    {
        dfn[u]=++tot,fx[u][0]=fa,dep[u]=dep[fa]+1;
        fo(i,1,20) fx[u][i]=fx[fx[u][i-1]][i-1];
        for(int i=hh[u];i!=-1;i=ne[i])
        {
            int v=to[i];
            if(v==fa) continue;
            Wdfs(v,u);
        }
    }
    int Wlca(int x,int y)
    {
        if(dep[x]<dep[y]) swap(x,y);
        fu(i,20,0) if(dep[fx[x][i]]>=dep[y]) x=fx[x][i];
        if(x==y) return x;
        fu(i,20,0) if(fx[x][i]!=fx[y][i]) x=fx[x][i],y=fx[y][i];
        return fx[x][0];
    }
    void Wsol(int u)
    {
        siz[u]=yz[u],g[u]=0;
        if(yz[u]) ma[u]=mi[u]=0;
        else mi[u]=(ll)1e18,ma[u]=(ll)-1e18;
        for(int i=hh[u];i!=-1;i=ne[i])
        {
            int v=to[i];
            Wsol(v);
            ll d=dep[v]-dep[u];
            ans+=(g[u]+siz[u]*d)*siz[v]+g[v]*siz[u];
            siz[u]+=siz[v],g[u]+=g[v]+d*siz[v];
            ansmi=min(ansmi,mi[u]+mi[v]+d),ansma=max(ansma,ma[u]+ma[v]+d);
            mi[u]=min(mi[u],mi[v]+d),ma[u]=max(ma[u],ma[v]+d);
        }
        hh[u]=-1;
    }
    short main()
    {
        // freopen(".in","r",stdin),freopen(".out","w",stdout);
        n=qr;
        memset(hh,-1,sizeof hh);
        fo(i,1,n-1)
        {
            int a=qr,b=qr;
            Wadd(a,b),Wadd(b,a);
        }
        Wdfs(1,0);
        m=qr;
        memset(hh,-1,sizeof hh);
        fo(i,1,m)
        {
            int tot=qr,len=0;cnt=0;
            fo(i,1,tot) zc[i]=qr,yz[zc[i]]=1;
            sort(zc+1,zc+1+tot,cmp);
            fo(i,1,tot-1) zc1[++len]=zc[i],zc1[++len]=Wlca(zc[i],zc[i+1]);
            zc1[++len]=zc[tot];
            sort(zc1+1,zc1+1+len,cmp);
            len=unique(zc1+1,zc1+1+len)-zc1-1;
            fo(i,1,len-1)
            {
                int lc=Wlca(zc1[i],zc1[i+1]);
                Wadd(lc,zc1[i+1]);
            }
            ans=0,ansmi=(ll)1e18,ansma=(ll)-1e18;
            Wsol(1);
            printf("%lld %lld %lld\n",ans,ansmi,ansma);
            fo(i,1,tot) yz[zc[i]]=0;
        }
        return Ratio;
    }
}
int main(){return Wisadel::main();}
2024/8/9 18:02
加载中...