BZOJ 3572 [HNOI2014]世界树 (虚树+DP)

题面：BZOJ传送门洛谷传送门

题目大意：略

细节贼多的虚树$DP$

先考虑只有一次询问的情况

一个节点$x$可能被它子树内的一个到x距离最小的特殊点管辖，还可能被管辖fa[x]的特殊点管辖

跑两次$dfs$即可，时间$O(n)$

再考虑一条链的情况

一条链上有很多个特殊点，相邻两个特殊点$x,y$之间可能有很多连续的非特殊点，那么在这些连续的非特殊点上会有一个分界，前面一部分被$x$管辖，后面一部分被$y$管辖

在链上二分即可，时间$O(mlogm)$

正解就是把上面两种情况结合起来..用虚树维护一下

首先根据套路对特殊点建出虚树，虚树上会出现所有的特殊点以及一些作为$LCA$的非特殊点。

用第一种情况的方法在虚树上搜索一遍，求出虚树上的每个节点被哪些节点管辖

再考虑剩余节点的贡献

对于虚树上相邻的两个节点$x,y$，假设$dep[x]<dep[y]$，我们取出原树上端点为$x,y$的链$F$，然后把$F$的两个端点$x,y$去掉，贡献分为两种情况

$x,y$被同一个的节点管辖，那么链F上的节点以及链F上挂着的子树也都会被这个节点管辖

$x,y$被不同的节点管辖，借用第二种情况的方法，链F上一定存在一个分界点，上面一部分被管辖x的节点管辖，下面一部分被管辖y的节点管辖，倍增跳一下即可

看起来很好写，实际上细节真的不少啊..上午迷迷糊糊写+调了4h才过

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define ll long long

 #define N1 300100

 using namespace std;

 const int inf=0x3f3f3f3f;

 template <typename _T> void read(_T &ret)

 {

     ret=; _T fh=; char c=getchar();

     while(c<''||c>''){ if(c=='-') fh=-; c=getchar(); }

     while(c>=''&&c<=''){ ret=ret*+c-''; c=getchar(); }

     ret=ret*fh;

 }

 template <typename _T> _T chkmin(_T &x,_T &y,_T vx,_T vy)

 {

     if(vx<vy) return x;

     if(vx>vy) return y;

     return x<y?x:y;

 }

 struct Edge{

 int to[N1*],nxt[N1*],head[N1],cte;

 void ae(int u,int v)

 { cte++; to[cte]=v; nxt[cte]=head[u]; head[u]=cte; } //val[cte]=w;

 void clr()

 { memset(to,,(cte+)*); memset(nxt,,(cte+)*); cte=; }

 }e,g;

 int n,de;

 int lg[N1*];

 int dep[N1],ff[N1][],eu[N1*][],st[N1],sz[N1],cur;

 void dfs(int x)

 {

     int j,v; ff[x][]=x; eu[st[x]=++cur][]=x;

     for(j=e.head[x];j;j=e.nxt[j])

     {

         v=e.to[j]; if(v==ff[x][]) continue;

         ff[v][]=x; dep[v]=dep[x]+;

         dfs(v);

         eu[++cur][]=x; sz[x]+=sz[v];

     }

     sz[x]++;

 }

 void get_st()

 {

     int i,j;

     for(j=;j<=;j++)

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

         ff[i][j]=ff[ ff[i][j-] ][j-];

     for(i=,lg[]=;i<=cur;i++) lg[i]=lg[i>>]+;

     for(j=;j<=lg[cur];j++)

     for(i=;i+(<<j)-<=cur;i++)

         eu[i][j]=dep[eu[i][j-]] < dep[eu[i+(<<(j-))][j-]] ? eu[i][j-] : eu[i+(<<(j-))][j-];

 }

 int LCA(int x,int y)

 {

     x=st[x], y=st[y]; if(x>y) swap(x,y); int l=y-x+;

     return dep[eu[x][lg[l]]] < dep[eu[y-(<<lg[l])+][lg[l]]] ? eu[x][lg[l]] : eu[y-(<<lg[l])+][lg[l]];

 }

 int Dis(int x,int y)

 {

     if(!x||!y) return inf; int F=LCA(x,y);

     return dep[x]+dep[y]-*dep[F];

 }

 int jump(int x,int D)

 {

     int i;

     for(i=lg[dep[x]-D]+;i>=;i--)

         if(ff[x][i] && dep[ff[x][i]]>=D) x=ff[x][i];

     return x;

 }

 namespace virtree{

 int cmp_dfsorder(int x,int y){ return st[x]<st[y]; }

 int vir[N1],num,stk[N1],tp,ctrl[N1],spe[N1],ans[N1],org[N1],dctrl[N1];

 void push(int x)

 {

     int y=stk[tp], F=LCA(x,y); stk[]=F;

     while(tp> && dep[stk[tp-]]>dep[F])

     {

         g.ae(stk[tp-],stk[tp]);

         stk[tp]=; tp--;

     }

     if(dep[stk[tp]]>dep[F])

     {

         g.ae(F,stk[tp]);

         stk[tp]=; tp--;

     }

     if(!tp||stk[tp]!=F) stk[++tp]=F;

     if(stk[tp]!=x) stk[++tp]=x;

 }

 int build()

 {

     int i;

     for(i=;i<=num;i++) spe[vir[i]]=, org[i]=vir[i];

     if(!spe[]) vir[++num]=;

     sort(vir+,vir+num+,cmp_dfsorder);

     stk[++tp]=vir[];

     for(i=;i<=num;i++) push(vir[i]);

     while(tp>) g.ae(stk[tp-],stk[tp]), tp--;

     return stk[tp];

 }

 int dfs_son(int x)

 {

     int j,v,mi=;

     for(j=g.head[x];j;j=g.nxt[j])

     {

         v=g.to[j]; dfs_son(v);

         mi=chkmin(ctrl[v],mi,dep[ctrl[v]],dep[mi]);

     }

     ctrl[x]=(spe[x]?x:mi);

     return ctrl[x];

 }

 void dfs_fa(int x)

 {

     int j,v;

     for(j=g.head[x];j;j=g.nxt[j])

     {

         v=g.to[j];

         ctrl[v]=chkmin(ctrl[x],ctrl[v],Dis(ctrl[x],v),Dis(ctrl[v],v));

         dfs_fa(v);

     }

 }

 void debug(int x)

 {

     int j,v;

     if(spe[x]) printf("%d ",x);

     for(j=e.head[x];j;j=e.nxt[j])

     {

         v=e.to[j]; if(v==ff[x][]) continue;

         debug(v);

     }

 }

 void dfs_ans(int x)

 {

     int j,v,sum=sz[x],cx=ctrl[x]; dctrl[x]=Dis(x,ctrl[x]);

     for(j=g.head[x];j;j=g.nxt[j])

     {

         v=g.to[j]; dfs_ans(v);

         int cv=ctrl[v],p,pv,tmp;

         pv=jump(v,dep[x]+);

         sum-=sz[pv];

         if(dep[v]==dep[x]+) continue;

         if(cx!=cv){

             tmp=dctrl[x]+dctrl[v]+dep[v]-dep[x];

             if(tmp&){

                 p=dep[v]-((tmp-)/-dctrl[v]);

                 p=jump(v, min(dep[v],max(dep[x]+,p)) );

             }else{

                 p=dep[v]-((tmp-)/-dctrl[v]);

                 if(p<=dep[v]){

                     p=jump(v, min(dep[v],max(dep[x]+,p)) );

                     if(cv<cx && dep[p]->=dep[x]+) p=ff[p][];

                 }else p=v;

             }

             ans[cx]+=sz[pv]-sz[p], ans[cv]+=sz[p]-sz[v];

         }else{

             ans[cx]+=sz[pv]-sz[v];

         }

     }

     ans[cx]+=sum;

 }

 void dfs_clear(int x)

 {

     int j,v;

     for(j=g.head[x];j;j=g.nxt[j])

     {

         v=g.to[j]; dfs_clear(v);

     }

     g.head[x]=ctrl[x]=spe[x]=ans[x]=;

 }

 void solve(int Num)

 {

     num=Num;

     int root=build(),i;

     dfs_son(root);

     dfs_fa(root);

     dfs_ans(root);

     for(i=;i<=Num;i++) if(i!=Num) printf("%d ",ans[org[i]]); else printf("%d\n",ans[org[i]]);

     dfs_clear(root);

     memset(vir,,(num+)*); memset(org,,(num+)*); memset(stk,,(tp+)*); g.clr(); tp=;

 }

 };

 int main()

 {

     int i,j,ans=,x,y,q,Q;

     scanf("%d",&n);

     for(i=;i<n;i++) read(x), read(y), e.ae(x,y), e.ae(y,x);

     dfs(); get_st(); dep[]=inf;

     scanf("%d",&Q);

     for(q=;q<=Q;q++)

     {

         read(x);

         for(i=;i<=x;i++) read(virtree::vir[i]);

         virtree::solve(x);

     }

     return ;

 }

巴特西

BZOJ 3572 [HNOI2014]世界树 (虚树+DP)

最新文章

热门文章