bzoj2286
虚树
如何构建虚树：
step1：将询问点按dfs序排好，root节点作为非关键点先入栈
step2：判断当前要加的点a[i]和sta[top]的关系
我们令lc=lca(a[i],sta[top]);
(1).如果lc在栈sta中并且就是栈顶的话，直接将a[i]加入栈
(2).如果lc在栈sta中但是不是栈顶的话,一直弹栈到lc(lc不弹)，且在弹栈的过程中加虚树边{sta[top-1],sta[top],w}，然后将a[i]加入栈
(3).lc不在栈sta中，弹栈一直弹到dfn[sta[top-1]]
注意每次要清空当前虚树的所有边(写的时候傻了for到n去清空了st，查了2小时)
/**************************************************************
Problem: 2286
User: syh0313
Language: C++
Result: Accepted
Time:11004 ms
Memory:45484 kb
****************************************************************/
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=250010;
int n,m,st[maxn<<1],nt[maxn<<1],to[maxn<<1],topt,dfn[maxn],dfn_num,a[maxn],sta[maxn],top;
int fa[22][maxn],lg[maxn],dep[maxn],key[maxn],q[maxn],cnt;
long long w[maxn<<1],dis[maxn],mi[maxn],dp[maxn];
bool f[maxn];
inline void add(int x,int y,long long z)
{to[++topt]=y; nt[topt]=st[x]; st[x]=topt; w[topt]=z;}
void dfs(int x)
{
f[x]=1; dfn[x]=++dfn_num; int p=st[x];
while (p)
{
if (!f[to[p]])
{
dis[to[p]]=dis[x]+w[p]; dep[to[p]]=dep[x]+1;
fa[0][to[p]]=x; mi[to[p]]=min(mi[x],w[p]); dfs(to[p]);
}
p=nt[p];
}
}
inline void init()
{
for (register int i=1;i<=maxn-10;i++) lg[i]=lg[i-1]+((1ll<<(lg[i-1]+1))==i);
for (register int i=1;i<=20;i++)
for (register int j=1;j<=n;j++) fa[i][j]=fa[i-1][fa[i-1][j]];
}
int lca(int x,int y)
{
if (dep[x]
while (dep[x]>dep[y]) {x=fa[lg[dep[x]-dep[y]]][x];}
if (x==y) return x;
for (register int i=20;i>=0;i--) if (fa[i][x]!=fa[i][y]) {x=fa[i][x]; y=fa[i][y];}
return fa[0][x];
}
inline bool cmp(int aa,int bb){return dfn[aa]
void tree_dp(int x,int fa)
{
long long now=0; int p=st[x];
if (key[x]) {dp[x]=mi[x]; return;}
while (p)
{
if (to[p]!=fa) {tree_dp(to[p],x); now+=dp[to[p]];}
p=nt[p];
}
dp[x]=min(mi[x],now);
}
inline int read()
{
int xx=0,ff=1; char c=getchar();
while (c<'0' || c>'9') {if (c=='-') ff=-1; c=getchar();}
while (c>='0' && c<='9') {xx=(xx<<1)+(xx<<3)+c-'0'; c=getchar();}
return xx*ff;
}
inline long long readl()
{
long long xx=0,ff=1; char c=getchar();
while (c<'0' || c>'9') {if (c=='-') ff=-1; c=getchar();}
while (c>='0' && c<='9') {xx=(xx<<1)+(xx<<3)+c-'0'; c=getchar();}
return xx*ff;
}
int main()
{
n=read(); for (register int i=0;i<=n;i++) mi[i]=1e18,dp[i]=1e18;
for (register int i=1;i
{
int xx,yy; long long zz; xx=read(); yy=read(); zz=readl();
add(xx,yy,zz); add(yy,xx,zz);
}
dfs(1); init(); m=read(); memset(f,0,sizeof f); memset(st,0,sizeof st);
while (m--)
{
topt=0; top=0; cnt=0; int num; num=read();
for (register int i=1;i<=num;i++) a[i]=read(),key[a[i]]=1;
a[++num]=1; sort(a+1,a+num+1,cmp); sta[++top]=a[1]; f[a[1]]=1;
for (register int i=2;i<=num;i++)
{
int lc=lca(sta[top],a[i]); q[++cnt]=lc;
if (f[lc])
{
while (top && sta[top]!=lc)
{
add(sta[top-1],sta[top],dis[sta[top]]-dis[sta[top-1]]);
f[sta[top]]=0; top--;
}
sta[++top]=a[i]; f[a[i]]=1;
}
else
{
while (top>=2 && dfn[sta[top]]>dfn[lc] && dfn[sta[top-1]]>dfn[lc])
{
add(sta[top-1],sta[top],dis[sta[top]]-dis[sta[top-1]]);
f[sta[top]]=0; top--; lc=lca(a[i],sta[top]);
}
add(lc,sta[top],dis[sta[top]]-dis[lc]); f[sta[top]]=0; top--;
sta[++top]=lc; f[lc]=1; sta[++top]=a[i]; f[a[i]]=1;
}
}
while (top)
{
if (top>=2) add(sta[top-1],sta[top],dis[sta[top]]-dis[sta[top-1]]);
f[sta[top]]=0; top--;
}
tree_dp(1,0); printf("%lld\n",dp[1]);
for (register int i=1;i<=num;i++) dp[a[i]]=1e18,key[a[i]]=0,f[a[i]]=0,st[a[i]]=0;
for (register int i=1;i<=cnt;i++) st[q[i]]=0;
}
return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！