BZOJ 2286 树链剖分+DFS序+虚树+树形DP

时间：2024-06-29 10:04:32

第一次学习虚树，就是把无关的点去掉。Ｓ里维护一条链即可。

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <algorithm>

 #define LL long long

 using namespace std;

 const LL Maxm=;

 const LL Maxn=;

 const LL Inf=1e60;

 struct Node {LL to,next,w;}edge[Maxm],edge2[Maxm];

 LL head[Maxn],head2[Maxn],dep[Maxn],H[Maxn],mark[Maxn],size[Maxn];

 LL top[Maxn],father[Maxn],f[Maxn],S[Maxn],mn[Maxn];

 LL cnt1,cnt2,tot,n,u,v,w,tp,m,K;

 bool vis[Maxn];

 inline void Add(LL u,LL v,LL w)

 {edge[cnt1].to=v;edge[cnt1].next=head[u];edge[cnt1].w=w;head[u]=cnt1++;

 edge[cnt1].to=u;edge[cnt1].next=head[v];edge[cnt1].w=w;head[v]=cnt1++;}

 inline void Add2(LL u,LL v)

 {if (u==v) return; edge2[cnt2].to=v;edge2[cnt2].next=head2[u];head2[u]=cnt2++;}

 inline LL Min(LL x,LL y) {return x>y?y:x;}

 inline void Get_Int(LL &x)

 {

     x=;  char ch=getchar(); LL f=;

     while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

     while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();} x*=f;

 }

 inline void Put_Int(LL x)

 {

     char ch[];  LL top=;

     if (x==) ch[++top]='';

     while (x) ch[++top]=x%+'',x/=;

     while (top) putchar(ch[top--]); putchar('\n');

 }

 //================================================

 void Dfs1(LL u)

 {

     mark[u]=++tot;vis[u]=true; size[u]=;

     for (LL i=head[u];i!=-;i=edge[i].next)

         if (!vis[edge[i].to])

         {

             dep[edge[i].to]=dep[u]+;

             father[edge[i].to]=u;

             mn[edge[i].to]=Min(mn[u],edge[i].w);

             Dfs1(edge[i].to);

             size[u]+=size[edge[i].to];

         }

 }

 void Dfs2(LL u,LL chain)

 {

     top[u]=chain; vis[u]=true; LL k=;

     for (int i=head[u];i!=-;i=edge[i].next)

         if (!vis[edge[i].to] && (size[edge[i].to]>size[k] || k==)) k=edge[i].to;

     if (k==) return;

     Dfs2(k,chain);

     for (int i=head[u];i!=-;i=edge[i].next)

         if (!vis[edge[i].to] && i!=k) Dfs2(edge[i].to,edge[i].to);

 }

 inline LL Lca(LL u,LL v)

 {

     while (true)

     {

         if (top[u]==top[v]) return dep[u]>dep[v]?v:u;

         if (dep[top[u]]>dep[top[v]]) u=father[top[u]];

         else v=father[top[v]];

     }

 }

 //=============================================================

 inline bool cmp(LL x,LL y) {return mark[x]<mark[y];}

 void Dp(LL u)

 {

     vis[u]=true; f[u]=mn[u]; LL ret=;

     for (int i=head2[u];i!=-;i=edge2[i].next)

     {

         Dp(edge2[i].to);

         ret+=f[edge2[i].to];

     }

     head2[u]=-;

     if (ret) f[u]=Min(f[u],ret);

 }

 void Solve()

 {

     Get_Int(K);

     for (int i=;i<=K;i++) Get_Int(H[i]);

     sort(H+,H+K+,cmp);

     tp=tot=; H[++tot]=H[];

     for (int i=;i<=K;i++)

         if (Lca(H[tot],H[i])!=H[tot]) H[++tot]=H[i];

     cnt2=;

     S[++tp]=;

     for (int i=;i<=tot;i++)

     {

         LL u=H[i],f=Lca(u,S[tp]);

         while (true)

         {

             if (dep[f]>=dep[S[tp-]])

             {

                 Add2(f,S[tp--]);

                 if (S[tp]!=f) S[++tp]=f;

                 break;

             }

             Add2(S[tp-],S[tp]); tp--;

         }

         if (S[tp]!=u) S[++tp]=u;

     }

     while (--tp) Add2(S[tp],S[tp+]);

     Dp();

     Put_Int(f[]);

 }

 int main()

 {

     Get_Int(n);

     memset(head,-,sizeof(head));cnt1=;

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

     {

         Get_Int(u),Get_Int(v),Get_Int(w);

         Add(u,v,w),Add(v,u,w);

     }

     father[]=; dep[]=; tot=; mn[]=Inf;

     memset(vis,false,sizeof(vis));Dfs1();

     memset(vis,false,sizeof(vis));Dfs2(,);

     memset(head2,-,sizeof(head2));

     Get_Int(m);

     for (int i=;i<=m;i++) Solve();

     return ;

 }

C++

相关文章