2 条题解

  • 0
    @ 2025-10-8 17:08:58
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int N=1e6+10,inf=0x3f3f3f3f;
    vector<int>G[N],G2[N];
    int n,k,a[N];
    int tsp,dfn[N],dep[N],D,st[N][20];
    void dfs(int x,int xfa)
    {
        dfn[x]=++tsp;
        dep[x]=dep[xfa]+1;
        st[x][0]=xfa;for(int i=1;i<=D;i++)st[x][i]=st[st[x][i-1]][i-1];
        for(int y:G[x])if(y!=xfa)dfs(y,x);
    }
    int LCA(int x,int y)
    {
        if(dep[x]<dep[y])swap(x,y);
        for(int i=D;i>=0;i--)if(dep[st[x][i]]>=dep[y])x=st[x][i];
        if(x==y)return x;
        for(int i=D;i>=0;i--)if(st[x][i]!=st[y][i])x=st[x][i],y=st[y][i];
        return st[x][0];
    }
    bool cmp(int x,int y){ return dfn[x]<dfn[y];}
    int sta[N],top;
    void build()
    {
        sort(a+1,a+k+1,cmp);
        sta[top=1]=1;if(a[1]!=1)sta[++top]=a[1];
        for(int i=2;i<=k;i++)
        {
            int lca=LCA(sta[top],a[i]);
            while(top>1 && !(dep[sta[top-1]]<dep[lca]))G2[sta[top-1]].push_back(sta[top]),top--;
            if(lca!=sta[top])G2[lca].push_back(sta[top]),top--,sta[++top]=lca;
            sta[++top]=a[i];
        }
        for(int i=1; i<top; i++)G2[sta[i]].push_back(sta[i+1]);
    }
    LL ans,mnn,mxx,mn[N],mx[N],g[N],siz[N];bool mk[N];
    void DP(int x)
    {
        if(mk[x]) mx[x]=mn[x]=0; else mx[x]=-inf,mn[x]=inf;
        siz[x]=mk[x];  g[x]=0;
        for(int y:G2[x])
        {
            DP(y);
            LL c=dep[y]-dep[x];
            ans+=c*siz[x]*siz[y] + g[x]*siz[y] + g[y]*siz[x];
            siz[x]+=siz[y];
            g[x]+=g[y]+c*siz[y];
            mnn=min(mnn,mn[x]+mn[y]+c);
            mxx=max(mxx,mx[x]+mx[y]+c);
            mn[x]=min(mn[x],mn[y]+c);
            mx[x]=max(mx[x],mx[y]+c);
        }
        G2[x].clear();
    }
    int main()
    {
        scanf("%d",&n);
        for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),G[x].push_back(y),G[y].push_back(x);
        tsp=0;dep[0]=0;D=log2(n);dfs(1,0);
        int q;scanf("%d",&q);
        memset(mk,0,sizeof(mk));
        while(q--)
        {
            scanf("%d",&k);
            for(int i=1;i<=k;i++)scanf("%d",&a[i]),mk[a[i]]=1;
            build();
            ans=0,mnn=inf,mxx=-inf; DP(1);
            printf("%lld %lld %lld\n",ans,mnn,mxx);
            for(int i=1;i<=k;i++)mk[a[i]]=0;
        }
        return 0;
    }
    
    • 0
      @ 2025-10-8 17:08:44
      #include<bits/stdc++.h>
      using namespace std;
      typedef long long LL;
      const int N=1e6+10,inf=0x3f3f3f3f;
      vector<int>G[N],G2[N];
      int n,k,a[N];
      int tsp,dfn[N],dep[N],D,st[N][20];
      void dfs(int x,int xfa)
      {
          dfn[x]=++tsp;
          dep[x]=dep[xfa]+1;
          st[x][0]=xfa;for(int i=1;i<=D;i++)st[x][i]=st[st[x][i-1]][i-1];
          for(int y:G[x])if(y!=xfa)dfs(y,x);
      }
      int LCA(int x,int y)
      {
          if(dep[x]<dep[y])swap(x,y);
          for(int i=D;i>=0;i--)if(dep[st[x][i]]>=dep[y])x=st[x][i];
          if(x==y)return x;
          for(int i=D;i>=0;i--)if(st[x][i]!=st[y][i])x=st[x][i],y=st[y][i];
          return st[x][0];
      }
      bool cmp(int x,int y){ return dfn[x]<dfn[y];}
      int sta[N],top;
      void build()
      {
          sort(a+1,a+k+1,cmp);
          sta[top=1]=1;if(a[1]!=1)sta[++top]=a[1];
          for(int i=2;i<=k;i++)
          {
              int lca=LCA(sta[top],a[i]);
              while(top>1 && !(dep[sta[top-1]]<dep[lca]))G2[sta[top-1]].push_back(sta[top]),top--;
              if(lca!=sta[top])G2[lca].push_back(sta[top]),top--,sta[++top]=lca;
              sta[++top]=a[i];
          }
          for(int i=1; i<top; i++)G2[sta[i]].push_back(sta[i+1]);
      }
      LL ans,mnn,mxx,mn[N],mx[N],g[N],siz[N];bool mk[N];
      void DP(int x)
      {
          if(mk[x]) mx[x]=mn[x]=0; else mx[x]=-inf,mn[x]=inf;
          siz[x]=mk[x];  g[x]=0;
          for(int y:G2[x])
          {
              DP(y);
              LL c=dep[y]-dep[x];
              ans+=c*siz[x]*siz[y] + g[x]*siz[y] + g[y]*siz[x];
              siz[x]+=siz[y];
              g[x]+=g[y]+c*siz[y];
              mnn=min(mnn,mn[x]+mn[y]+c);
              mxx=max(mxx,mx[x]+mx[y]+c);
              mn[x]=min(mn[x],mn[y]+c);
              mx[x]=max(mx[x],mx[y]+c);
          }
          G2[x].clear();
      }
      int main()
      {
          scanf("%d",&n);
          for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),G[x].push_back(y),G[y].push_back(x);
          tsp=0;dep[0]=0;D=log2(n);dfs(1,0);
          int q;scanf("%d",&q);
          memset(mk,0,sizeof(mk));
          while(q--)
          {
              scanf("%d",&k);
              for(int i=1;i<=k;i++)scanf("%d",&a[i]),mk[a[i]]=1;
              build();
              ans=0,mnn=inf,mxx=-inf; DP(1);
              printf("%lld %lld %lld\n",ans,mnn,mxx);
              for(int i=1;i<=k;i++)mk[a[i]]=0;
          }
          return 0;
      }
      • 1

      信息

      ID
      5276
      时间
      2000ms
      内存
      256MiB
      难度
      9
      标签
      递交数
      291
      已通过
      32
      上传者