「BZOJ3611」[HEOI2014] 大工程

2015年1月20日6,1572

题面和题解见http://www.cnblogs.com/zyfzyf/p/4231356.html

#include<iostream>
#include<set>
#include<map>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#define inf 2000000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll tot;
int bin[20];
int n,K,top,cnt,q,ind,ans1,ans2;
int last[1000005],last2[1000005],v[1000005];
int mx[1000005],mn[1000005];
int fa[1000005][20],deep[1000005],mark[1000005],st[1000005],h[1000005];
ll size[1000005],f[1000005];
struct edge{
	int to,next,v;
}e[2000005],ed[2000005];
void insert(int u,int v)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
	e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;
}
void insert2(int u,int v)
{
	if(u==v)return;
	ed[++cnt].to=v;ed[cnt].next=last2[u];last2[u]=cnt;ed[cnt].v=deep[v]-deep[u];
}
void pre(int x)
{
	mark[x]=++ind;
	for(int i=1;bin[i]<=deep[x];i++)
		fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa[x][0])
		{
			deep[e[i].to]=deep[x]+1;
			fa[e[i].to][0]=x;
			pre(e[i].to);
		}
}
int lca(int x,int y)
{
	if(deep[x]<deep[y])swap(x,y);
	int t=deep[x]-deep[y];
	for(int i=0;bin[i]<=t;i++)
		if(bin[i]&t)x=fa[x][i];
	for(int i=19;i>=0;i--)
		if(fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
	if(x==y)return x;
	return fa[x][0];
}
bool cmp(int a,int b)
{
	return mark[a]<mark[b];
}
void dp(int x)
{
	int tmp=0;
	size[x]=v[x];f[x]=0;
	mn[x]=v[x]?0:inf;
	mx[x]=v[x]?0:-inf;
	for(int i=last2[x];i;i=ed[i].next)
	{
		int y=ed[i].to;		
		dp(y);
		tot+=(f[x]+size[x]*ed[i].v)*size[y]+f[y]*size[x];
		size[x]+=size[y];
		f[x]+=f[y]+ed[i].v*size[y];
		ans1=min(ans1,mn[x]+mn[y]+ed[i].v);
		ans2=max(ans2,mx[x]+mx[y]+ed[i].v);
		mn[x]=min(mn[x],mn[y]+ed[i].v);
		mx[x]=max(mx[x],mx[y]+ed[i].v);
	}
	last2[x]=0;
}
void solve()
{
	K=read();
	for(int i=1;i<=K;i++)h[i]=read();
	for(int i=1;i<=K;i++)v[h[i]]=1;
	sort(h+1,h+K+1,cmp);
	top=cnt=0;
	int x,f;
	st[++top]=1;
	for(int i=1;i<=K;i++)
	{
		x=h[i];f=lca(x,st[top]);
		if(f==st[top]){st[++top]=x;continue;}
		while(f==lca(x,st[top-1]))
		{
			insert2(st[top-1],st[top]);
			top--;f=lca(x,st[top]);
		}
		insert2(f,st[top]);
		st[top]=f;st[++top]=x;
	}
	while(--top)insert2(st[top],st[top+1]);
	ans1=inf;ans2=-inf;tot=0;
	dp(1);
	printf("%lld %d %d\n",tot,ans1,ans2);
	for(int i=1;i<=K;i++)v[h[i]]=0;
}
int main()
{
	bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;
	n=read();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read();
		insert(u,v);
	}
	pre(1);
	q=read();
	while(q--)solve();
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

#include<iostream>

#include<set>

#include<map>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<cmath>

#define inf 2000000000

#define pa pair<int,int>

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

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

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

return x*f;

}

ll tot;

int bin[20];

int n,K,top,cnt,q,ind,ans1,ans2;

int last[1000005],last2[1000005],v[1000005];

int mx[1000005],mn[1000005];

int fa[1000005][20],deep[1000005],mark[1000005],st[1000005],h[1000005];

ll size[1000005],f[1000005];

struct edge{

int to,next,v;

}e[2000005],ed[2000005];

void insert(int u,int v)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;

e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;

}

void insert2(int u,int v)

{

if(u==v)return;

ed[++cnt].to=v;ed[cnt].next=last2[u];last2[u]=cnt;ed[cnt].v=deep[v]-deep[u];

}

void pre(int x)

{

mark[x]=++ind;

for(int i=1;bin[i]<=deep[x];i++)

fa[x][i]=fa[fa[x][i-1]][i-1];

for(int i=last[x];i;i=e[i].next)

if(e[i].to!=fa[x][0])

{

deep[e[i].to]=deep[x]+1;

fa[e[i].to][0]=x;

pre(e[i].to);

}

int lca(int x,int y)

{

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

int t=deep[x]-deep[y];

for(int i=0;bin[i]<=t;i++)

if(bin[i]&t)x=fa[x][i];

for(int i=19;i>=0;i--)

if(fa[x][i]!=fa[y][i])

x=fa[x][i],y=fa[y][i];

if(x==y)return x;

return fa[x][0];

}

bool cmp(int a,int b)

{

return mark[a]<mark[b];

}

void dp(int x)

{

int tmp=0;

size[x]=v[x];f[x]=0;

mn[x]=v[x]?0:inf;

mx[x]=v[x]?0:-inf;

for(int i=last2[x];i;i=ed[i].next)

{

int y=ed[i].to;

dp(y);

tot+=(f[x]+size[x]*ed[i].v)*size[y]+f[y]*size[x];

size[x]+=size[y];

f[x]+=f[y]+ed[i].v*size[y];

ans1=min(ans1,mn[x]+mn[y]+ed[i].v);

ans2=max(ans2,mx[x]+mx[y]+ed[i].v);

mn[x]=min(mn[x],mn[y]+ed[i].v);

mx[x]=max(mx[x],mx[y]+ed[i].v);

}

last2[x]=0;

}

void solve()

{

K=read();

for(int i=1;i<=K;i++)h[i]=read();

for(int i=1;i<=K;i++)v[h[i]]=1;

sort(h+1,h+K+1,cmp);

top=cnt=0;

int x,f;

st[++top]=1;

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

{

x=h[i];f=lca(x,st[top]);

if(f==st[top]){st[++top]=x;continue;}

while(f==lca(x,st[top-1]))

{

insert2(st[top-1],st[top]);

top--;f=lca(x,st[top]);

}

insert2(f,st[top]);

st[top]=f;st[++top]=x;

}

while(--top)insert2(st[top],st[top+1]);

ans1=inf;ans2=-inf;tot=0;

dp(1);

printf("%lld %d %d\n",tot,ans1,ans2);

for(int i=1;i<=K;i++)v[h[i]]=0;

}

int main()

{

bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;

n=read();

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

{

int u=read(),v=read();

insert(u,v);

}

pre(1);

q=read();

while(q--)solve();

return 0;

}

« 「BZOJ2286」[SDOI2011] 消耗战「BZOJ3772」精神污染 »

zyt

黄学长dp中的f数组记录的是什么？

虚树 | Chenyao's Blog

[…] bzoj3611: [HEOI2014]大工程和上题类似,建出虚树. 对于求和:记录每个点为根时,这个点及其后代的询问点个数sz[u],然后每条边的贡献为sz[u]*(M-sz[u]) 对于求最大值:计算每个点距离最远后代的距离,第二远的距离.然后再计算从父亲来的最远距离.然后对于每条边(u,fa)最远距离为mx1[u]+fmx+len(u,fa).fmx为fa距离不是u及其u后代的点的最远距离. 对于最小值:类似于最大值. UPD: 搜了题解,发现自己傻逼了…那个…其实求最值得时候,可以直接求嘛…因为对于在树上弯曲的路径,其实还是可以在路径最高点求出来的… HZWER的代码 […]

hzwer.com _ Home | http://hzwer.com

「BZOJ3611」[HEOI2014] 大工程

分类目录

热门文章

Myfriends

近期评论