求助,TLE 80pts
查看原帖
求助,TLE 80pts
308729
sheeplittlecloud楼主2023/10/8 21:27
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
const int N=2e6+7;
struct node
{
    int to,nxt,w,fr;
}e1[N],e[N];//e yuan e1 xushu 
int head[N],head1[N],cnt1,cnt2;
void add(int u,int v)
{
    e[++cnt1].to=v;
    e[cnt1].nxt=head[u];
    head[u]=cnt1;
}
void add1(int u,int v,int w)
{
    e1[++cnt2].to=v;
    e1[cnt2].nxt=head1[u];
    head1[u]=cnt2;
    e1[cnt2].w=w;
    e1[cnt2].fr=u;
}
int q,k;
int dot[N];
int fa[N],siz[N],son[N],dfn[N],id[N],top[N],dep[N];
void dfs1(int x)
{
	dep[x]=dep[fa[x]]+1;
	siz[x]=1;
	for(int i=head[x];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa[x]) continue;
		fa[v]=x;
		dfs1(v);
		siz[x]+=siz[v];
		if(!son[x]||siz[x]>siz[son[x]])
			son[x]=v;
	}
	return ;
}
int cnt;
void dfs2(int x,int d)
{
	top[x]=d;
	dfn[x]=++cnt;
	id[dfn[x]]=x;
	if(son[x]) dfs2(son[x],d);
	for(int i=head[x];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(fa[x]!=v&&son[x]!=v)
			dfs2(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]];
	}
	if(dep[x]<dep[y]) return x;
	else return y;
}
bool cmp(int x,int y)
{
    return dfn[x]<dfn[y];
}
int stk[N],tot;
int rot;
int f[N],g[N];
int flag[N];
int ans1,ans2;
int dp[N];
void dfs(int x)
{
    if(flag[x])
    {
        f[x]=0;
        g[x]=0;
        siz[x]=1;
    }
    else
    {
        f[x]=-0x3f3f3f3f;
        g[x]=0x3f3f3f3f;
        siz[x]=0;
    }
    for(int i=head1[x];i;i=e1[i].nxt)
    {
        int v=e1[i].to;
        dfs(v);
        siz[x]+=siz[v];
        dp[x]+=dp[v];
        dp[x]+=(dep[v]-dep[x])*(k-1-siz[v])*siz[v];
        ans1=min(ans1,g[x]+g[v]+e1[i].w);
        ans2=max(ans2,f[x]+f[v]+e1[i].w);
        g[x]=min(g[x],g[v]+e1[i].w);
        f[x]=max(f[x],f[v]+e1[i].w);
    }
}
int tr[N];
int num;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    cin>>q;
    dfs1(1);
    dfs2(1,1);
    while(q--)
    {
        num=0;
        tot=0;
        rot=0;
        cin>>k;
        for(int i=1;i<=k;i++) {cin>>dot[i];flag[dot[i]]=1;}
        dot[++k]=1;
        sort(dot+1,dot+1+k,cmp);
        for(int i=1;i<k;i++)
        {
            stk[++tot]=dot[i];
            stk[++tot]=LCA(dot[i],dot[i+1]);
        }
        stk[++tot]=dot[k];
        sort(stk+1,stk+1+tot,cmp);
        tot=unique(stk+1,stk+1+tot)-stk-1;
        dfn[0]=0x3f3f3f3f;
        for(int i=1;i<tot;i++)
        {
            int lca=(LCA(stk[i],stk[i+1]));
            add1(lca,stk[i+1],dep[stk[i+1]]-dep[lca]);
            tr[++num]=lca;
            tr[++num]=stk[i+1];
            // cout<<lca<<"  "<<stk[i+1]<<endl;
        }
        ans1=0x3f3f3f3f;
        ans2=0;
        dfs(1);
        int ans=0;
        for(int i=1;i<=cnt2;i++)
        {
            ans=ans+(siz[e1[i].to]*(k-siz[e1[i].to]))*e1[i].w;
        }
        cout<<dp[1]<<" ";
        cout<<ans1<<" ";
        cout<<ans2<<'\n';
        for(int i=1;i<=k;i++) {flag[dot[i]]=0;}
        for(int i=1;i<=num;i++) 
        {
            dp[tr[i]]=0;
            siz[tr[i]]=0;
            if(i&1) head1[tr[i]]=0;
        }
        cnt2=0;
    }
    return 0;
}
/*
10 
2 1 
3 2
4 1
5 2
6 4
7 5
8 6
9 7
10 9
5
3
3 6 10
10 4 4
*/
2023/10/8 21:27
加载中...