AC日记——[SDOI2011]消耗战 洛谷 P2495

[SDOI2011]消耗战

思路；

　　建虚树走树形dp；

代码：

#include <bits/stdc++.h>

using namespace std;

#define INF 1e17

#define maxn 250005

#define ll long long

#define maxm (maxn<<1)

struct LandType {

    ll id,key;

    bool operator<(const LandType pos)const

    {

        return key<pos.key;

    }

};

struct LandType ai[maxn];

ll n,head[maxn],E[maxm],V[maxm],W[maxm],cnt;

ll size[maxn],top[maxn],f[maxn],deep[maxn];

ll lar[maxn],m,id[maxn],dis[maxn],li[maxn];

ll ri[maxn],sta[maxn];

bool if_[maxn];

inline void in(ll &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'')Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

inline void edge_add(ll u,ll v,ll w)

{

    E[++cnt]=head[u],V[cnt]=v,W[cnt]=w,head[u]=cnt;

    E[++cnt]=head[v],V[cnt]=u,W[cnt]=w,head[v]=cnt;

}

inline void edge_add(ll u,ll v)

{

//    printf("%d %d\n",u,v);

    E[++cnt]=head[u],V[cnt]=v,head[u]=cnt;

    E[++cnt]=head[v],V[cnt]=u,head[v]=cnt;

}

void dfs1(ll now,ll fa,ll pi)

{

    deep[now]=deep[fa]+,f[now]=fa;

    dis[now]=pi,size[now]=;

    for(ll i=head[now];i;i=E[i])

    {

        if(V[i]==fa) continue;

        dfs1(V[i],now,min(pi,W[i]));

        size[now]+=size[V[i]];

        if(size[V[i]]>size[lar[now]])lar[now]=V[i];

    }

}

void dfs2(ll now,ll chain)

{

    top[now]=chain,id[now]=++cnt,li[now]=cnt;

    if(lar[now])

    {

        dfs2(lar[now],chain);

        for(ll i=head[now];i;i=E[i])

        {

            if(V[i]==f[now]||V[i]==lar[now]) continue;

            dfs2(V[i],V[i]);

        }

    }

    ri[now]=cnt;

}

inline ll find(ll x,ll y)

{

    while(top[x]!=top[y])

    {

        if(deep[top[x]]<deep[top[y]]) swap(x,y);

        x=f[top[x]];

    }

    return deep[x]<deep[y]?x:y;

}

ll dp(ll now,ll fa)

{

    bool flag=false;

    ll pos=;

    for(ll i=head[now];i;i=E[i])

    {

        if(V[i]==fa) continue;

        pos+=dp(V[i],now),flag=true;

    }

    bool myj=if_[now];head[now]=;if_[now]=false;

    if(flag&&!myj) return min(pos,dis[now]);

    else return dis[now];

}

int main()

{

    in(n);ll u,v,w,ki;

    for(ll i=;i<n;i++)in(u),in(v),in(w),edge_add(u,v,w);

    cnt=,dfs1(,,INF),dfs2(,),in(m);

    memset(if_,,sizeof(if_));memset(head,,sizeof(head));

    while(m--)

    {

        in(ki),cnt=;

        for(ll i=;i<=ki;i++) in(ai[i].id),ai[i].key=id[ai[i].id],if_[ai[i].id]=true;

        sort(ai+,ai+ki+);ll p=;sta[p]=;

        for(ll i=;i<=ki;i++)

        {

            ll now=ai[i].id,pos=sta[p],pos_=sta[p-];

            if(id[now]>li[pos]&&id[now]<=ri[pos]) sta[++p]=now;

            else

            {

                if(id[now]>li[pos_]&&id[now]<=ri[pos_])

                {

                    ll lca=find(now,pos);

                    if(pos!=lca) edge_add(pos,lca);

                    p--;

                    if(lca!=pos_) sta[++p]=lca;

                    sta[++p]=now;

                }

                else

                {

                    while((id[now]<li[pos_]||id[now]>ri[pos_])&&p>)

                    {

                        edge_add(pos_,pos),p--;

                        pos=sta[p],pos_=sta[p-];

                    }

                    ll lca=find(now,pos);

                    edge_add(lca,pos),p--;

                    if(pos_!=lca) sta[++p]=lca;

                    sta[++p]=now;

                }

            }

        }

        while(p>)

        edge_add(sta[p],sta[p-]),p--;

        printf("%lld\n",dp(,));

    }

    return ;

}