[HEOI2014][bzoj3611] 大工程 [虚树+dp]

题面：

传送门

思路：

又是一道虚树入门级的题目，但是这道题的实际难点在于dp

首先，这道题是可以点分治做的，而且因为6s时限随便浪，所以写点分治也不是不可以

但是，dp因为$O\left(n\right)$的高效率，依然最好优先考虑

对于这道题的dp，我们首先记录几个数组：

siz[u]表示以u为根（包括u）的子树中，询问点的总个数

minn[u]表示子树中最短的一条由子树根到询问点的路径，maxn[u]则是最长的

sum[u]则代表这棵子树中所有要求路径的长度总和

最小路径和最大路径的dp都比较简单了

每次进入子树dp结束以后，用minn[v]更新minn[u]，然后用minn[u]+minn[v]+dis(u,v)更新答案

maxn同理

注意这里虽然是单位边权，但是建完虚树以后边的长度便不再固定是1了

sum的dp比较麻烦一点

每次子树v的dp结束以后，先把siz[u]+=siz[v]，然后sum[u]+=sum[v]+siz[v]*(m-siz[v])*dis(u,v)

这里的m是本次询问的所有点数

这里相当于是把v子树中的所有路径（内部的路径）的值，加上经过(u,v)这条边的路径总数乘以dis(u,v)，然后加入到了总答案中

这样每个sum都会包含每条边应该经过的次数，答案是正确的

虚树建立起来以后，直接dp就可以了。注意这道题里面不能固定以1作为起点，因为路径很可能不经过1，所以需要另一种建立虚树的方法，详见代码

Code：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define ll long long

 #define inf 1e18

 using namespace std;

 inline ll read(){

     ll re=,flag=;char ch=getchar();

     while(ch>''||ch<''){

         if(ch=='-') flag=-;

         ch=getchar();

     }

     while(ch>=''&&ch<='') re=(re<<)+(re<<)+ch-'',ch=getchar();

     return re*flag;

 }

 ll n,m,dep[],st[][],dfn[],clk;

 ll sum[],minn[],maxn[],siz[];

 struct graph{

     ll first[],cnt;

     struct edge{

         ll to,next;

     }a[];

     graph(){

         memset(first,-,sizeof(first));cnt=;

     }

     void init(){cnt=;}

     inline void add(ll u,ll v){

         if(u==v) return;

         a[++cnt]=(edge){v,first[u]};first[u]=cnt;

     }

 }G,g;

 void dfs(ll u,ll f){

     ll i,v;

     dep[u]=dep[f]+;dfn[u]=++clk;st[u][]=f;

     for(i=G.first[u];~i;i=G.a[i].next){

         v=G.a[i].to;

         if(v==f) continue;

         dfs(v,u);

     }

 }

 void ST(){

     ll i,j;

     for(j=;j<=;j++) for(i=;i<=n;i++) st[i][j]=st[st[i][j-]][j-];

 }

 ll lca(ll l,ll r){

     if(dep[l]>dep[r]) swap(l,r);

     ll i;

     for(i=;i>=;i--) if(dep[st[r][i]]>=dep[l]) r=st[r][i];

     if(l==r) return l;

     for(i=;i>=;i--)

         if(st[l][i]!=st[r][i]){

             l=st[l][i];

             r=st[r][i];

         }

     return st[l][];

 }

 ll q[],s[],top,ans1,ans2,ans3;

 bool vis[];

 bool cmp(ll l,ll r){

     return dfn[l]<dfn[r];

 }

 void dp(ll u){

     ll i,v,dis;

     sum[u]=;minn[u]=inf;maxn[u]=;siz[u]=(vis[u]);

     for(i=g.first[u];~i;i=g.a[i].next){

         v=g.a[i].to;g.first[u]=g.a[i].next;

         dp(v);dis=dep[v]-dep[u];

         ans2=min(ans2,minn[u]+minn[v]+dis);minn[u]=min(minn[u],minn[v]+dis);

         ans3=max(ans3,maxn[u]+maxn[v]+dis);maxn[u]=max(maxn[u],maxn[v]+dis);

         siz[u]+=siz[v];

         sum[u]+=sum[v]+siz[v]*(m-siz[v])*dis;

     }

     if(vis[u]) vis[u]=,ans2=min(ans2,minn[u]),ans3=max(ans3,maxn[u]),minn[u]=;

 }

 void solve(){

     m=read();ll i,j,grand;g.init();

     for(i=;i<=m;i++) q[i]=read(),vis[q[i]]=;

     sort(q+,q+m+,cmp);top=;

     for(i=;i<=m;i++){

         if(!top){s[++top]=q[i];continue;}//因为现在没有一个1号结点压在栈底不可能弹出，所以需要检测栈是否为空

         grand=lca(q[i],s[top]);

         while(){

             if(dep[s[top-]]<=dep[grand]){

                 g.add(grand,s[top--]);

                 if(s[top]!=grand) s[++top]=grand;

                 break;

             }

             g.add(s[top-],s[top]);top--;

         }

         if(s[top]!=q[i]) s[++top]=q[i];

     }

     while(--top>=) g.add(s[top],s[top+]);

     ans1=ans3=;ans2=inf;

     dp(s[]);//这里从栈中最后剩下的元素开始dp，因为它就是整棵虚树的根了

     printf("%lld %lld %lld\n",sum[s[]],ans2,ans3);

     return;

 }

 int main(){

     ll i,j,t1,t2;n=read();

     for(i=;i<n;i++){

         t1=read(),t2=read();

         G.add(t1,t2);G.add(t2,t1);

     }

     dfs(,);ST();

     ll q=read();

     for(i=;i<=q;i++) solve();

 }

巴特西

[HEOI2014][bzoj3611] 大工程 [虚树+dp]

最新文章

热门文章