首页 > 代码库 > AC日记——[SDOI2011]消耗战 洛谷 P2495
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=0; while(Cget>‘9‘||Cget<‘0‘)Cget=getchar(); while(Cget>=‘0‘&&Cget<=‘9‘) { now=now*10+Cget-‘0‘; 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]+1,f[now]=fa; dis[now]=pi,size[now]=1; 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=0; 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]=0;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=1;i<n;i++)in(u),in(v),in(w),edge_add(u,v,w); cnt=0,dfs1(1,0,INF),dfs2(1,1),in(m); memset(if_,0,sizeof(if_));memset(head,0,sizeof(head)); while(m--) { in(ki),cnt=0; for(ll i=1;i<=ki;i++) in(ai[i].id),ai[i].key=id[ai[i].id],if_[ai[i].id]=true; sort(ai+1,ai+ki+1);ll p=1;sta[p]=1; for(ll i=1;i<=ki;i++) { ll now=ai[i].id,pos=sta[p],pos_=sta[p-1]; 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>1) { edge_add(pos_,pos),p--; pos=sta[p],pos_=sta[p-1]; } ll lca=find(now,pos); edge_add(lca,pos),p--; if(pos_!=lca) sta[++p]=lca; sta[++p]=now; } } } while(p>1) edge_add(sta[p],sta[p-1]),p--; printf("%lld\n",dp(1,0)); } return 0;}
AC日记——[SDOI2011]消耗战 洛谷 P2495
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。