「BZOJ3757」苹果树

2014年11月28日10,0710

Description

神犇家门口种了一棵苹果树。苹果树作为一棵树，当然是呈树状结构，每根树枝连接两个苹果，每个苹果都可以沿着一条由树枝构成的路径连到树根，而且这样的路径只存在一条。由于这棵苹果树是神犇种的，所以苹果都发生了变异，变成了各种各样的颜色。我们用一个到n之间的正整数来表示一种颜色。树上一共有n个苹果。每个苹果都被编了号码，号码为一个1到n之间的正整数。我们用0代表树根。只会有一个苹果直接根。

有许许多多的人来神犇家里膜拜神犇。可神犇可不是随便就能膜拜的。前来膜拜神犇的人需要正确回答一个问题，才能进屋膜拜神犇。这个问题就是，从树上编号为u的苹果出发，由树枝走到编号为v的苹果，路径上经过的苹果一共有多少种不同的颜色（包括苹果u和苹果v的颜色）？不过神犇注意到，有些来膜拜的人患有色盲症。具体地说，一个人可能会认为颜色a就是颜色b，那么他们在数苹果的颜色时，如果既出现了颜色a的苹果，又出现了颜色b的苹果，这个人只会算入颜色b，而不会把颜色a算进来。

神犇是一个好人，他不会强人所难，也就会接受由于色盲症导致的答案错误（当然答案在色盲环境下也必须是正确的）。不过这样神犇也就要更改他原先数颜色的程序了。虽然这对于神犇来说是小菜一碟，但是他想考验一下你。你能替神犇完成这项任务吗？

Input

输入第一行为两个整数n和m，分别代表树上苹果的个数和前来膜拜的人数。

接下来的一行包含n个数，第i个数代表编号为i的苹果的颜色Coli。

接下来有n行，每行包含两个数x和y，代表有一根树枝连接了苹果x和y（或者根和一个苹果）。

接下来有m行，每行包含四个整数u、v、a和b，代表这个人要数苹果u到苹果v的颜色种数，同时这个人认为颜色a就是颜色b。如果a=b=0，则代表这个人没有患色盲症。

Output

输出一共m行，每行仅包含一个整数，代表这个人应该数出的颜色种数。

Sample Input

5 3
1 1 3 3 2
0 1
1 2
1 3
2 4
3 5
1 4 0 0
1 4 1 3
1 4 1 2

Sample Output

2
1
2

HINT

0<=x,y,a,b<=N

N<=50000

1<=U,V,Coli<=N

题解

膜拜了KuribohG后的新技能。。。

http://blog.csdn.net/kuribohG/article/details/41458639

树上莫队

参照下vfk糖果公园的题解

http://vfleaking.blog.163.com/blog/static/174807634201311011201627/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<queue>
#include<cmath>
#include<algorithm>
#define inf 1000000000
#define ll long long
using namespace std;
inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int bin[20];
int n,m,cnt,ans;
int top,ind,blo,blonum,root;
int res[100005],p[50005];
int fa[50005][17],deep[50005];
int c[50005],st[50005],dfn[50005],belong[50005];
bool vis[50005];
struct data{int to,next;}e[100005];int last[50005];
struct query{int u,v,a,b,id;}q[100005];
bool operator<(query a,query b)
{
	if(belong[a.u]==belong[b.u])return dfn[a.v]<dfn[b.v];
	else return belong[a.u]<belong[b.u];
}
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;
}
int dfs(int x)
{
	int size=0;
    dfn[x]=++ind;
	for(int i=1;i<=16;i++)
		if(deep[x]>=bin[i])
			fa[x][i]=fa[fa[x][i-1]][i-1];
		else break;
	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;
			size+=dfs(e[i].to);
			if(size>=blo)
			{
				blonum++;
				for(int k=1;k<=size;k++)
					belong[st[top--]]=blonum;
				size=0;
			}
		}
	st[++top]=x;
	return size+1;
}
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(t&bin[i])x=fa[x][i];
	for(int i=16;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];
}
void reverse(int x)
{
	if(!vis[x]){vis[x]=1;p[c[x]]++;if(p[c[x]]==1)ans++;}
	else {vis[x]=0;p[c[x]]--;if(p[c[x]]==0)ans--;}
}
void solve(int u,int v)
{
	while(u!=v)
		if(deep[u]>deep[v])reverse(u),u=fa[u][0];
		else reverse(v),v=fa[v][0];
}
int main()
{
	bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;
	n=read();m=read();
	blo=sqrt(n);
	for(int i=1;i<=n;i++)c[i]=read();
	for(int i=1;i<=n;i++)
	{
		int u=read(),v=read();
		if(!u)root=v;
		else if(!v)root=u;
		else insert(u,v);
	}
	dfs(root);
	blonum++;
	while(top)belong[st[top--]]=blonum;
	for(int i=1;i<=m;i++)
	{
		q[i].u=read();q[i].v=read();
		if(dfn[q[i].u]>dfn[q[i].v])swap(q[i].u,q[i].v);
		q[i].a=read();q[i].b=read();
		q[i].id=i;
	}
	sort(q+1,q+m+1);
	int t=lca(q[1].u,q[1].v);
	solve(q[1].u,q[1].v);
	reverse(t);
	res[q[1].id]=ans;
	if(p[q[1].a]&&p[q[1].b]&&q[1].a!=q[1].b)res[q[1].id]--;
	reverse(t);
	for(int i=2;i<=m;i++)
	{
		solve(q[i-1].u,q[i].u);
		solve(q[i-1].v,q[i].v);
		t=lca(q[i].u,q[i].v);
		reverse(t);
		res[q[i].id]=ans;
		if(p[q[i].a]&&p[q[i].b]&&q[i].a!=q[i].b)res[q[i].id]--;
		reverse(t);
	}
	for(int i=1;i<=m;i++)
		printf("%d\n",res[i]);
	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

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<queue>

#include<cmath>

#include<algorithm>

#define inf 1000000000

#define ll long long

using namespace std;

inline int read()

{

int x=0;char ch=getchar();

while(ch<'0'||ch>'9')ch=getchar();

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

return x;

}

int bin[20];

int n,m,cnt,ans;

int top,ind,blo,blonum,root;

int res[100005],p[50005];

int fa[50005][17],deep[50005];

int c[50005],st[50005],dfn[50005],belong[50005];

bool vis[50005];

struct data{int to,next;}e[100005];int last[50005];

struct query{int u,v,a,b,id;}q[100005];

bool operator<(query a,query b)

{

if(belong[a.u]==belong[b.u])return dfn[a.v]<dfn[b.v];

else return belong[a.u]<belong[b.u];

}

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;

}

int dfs(int x)

{

int size=0;

dfn[x]=++ind;

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

if(deep[x]>=bin[i])

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

else break;

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;

size+=dfs(e[i].to);

if(size>=blo)

{

blonum++;

for(int k=1;k<=size;k++)

belong[st[top--]]=blonum;

size=0;

}

st[++top]=x;

return size+1;

}

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(t&bin[i])x=fa[x][i];

for(int i=16;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];

}

void reverse(int x)

{

if(!vis[x]){vis[x]=1;p[c[x]]++;if(p[c[x]]==1)ans++;}

else {vis[x]=0;p[c[x]]--;if(p[c[x]]==0)ans--;}

}

void solve(int u,int v)

{

while(u!=v)

if(deep[u]>deep[v])reverse(u),u=fa[u][0];

else reverse(v),v=fa[v][0];

}

int main()

{

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

n=read();m=read();

blo=sqrt(n);

for(int i=1;i<=n;i++)c[i]=read();

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

{

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

if(!u)root=v;

else if(!v)root=u;

else insert(u,v);

}

dfs(root);

blonum++;

while(top)belong[st[top--]]=blonum;

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

{

q[i].u=read();q[i].v=read();

if(dfn[q[i].u]>dfn[q[i].v])swap(q[i].u,q[i].v);

q[i].a=read();q[i].b=read();

q[i].id=i;

}

sort(q+1,q+m+1);

int t=lca(q[1].u,q[1].v);

solve(q[1].u,q[1].v);

reverse(t);

res[q[1].id]=ans;

if(p[q[1].a]&&p[q[1].b]&&q[1].a!=q[1].b)res[q[1].id]--;

reverse(t);

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

{

solve(q[i-1].u,q[i].u);

solve(q[i-1].v,q[i].v);

t=lca(q[i].u,q[i].v);

reverse(t);

res[q[i].id]=ans;

if(p[q[i].a]&&p[q[i].b]&&q[i].a!=q[i].b)res[q[i].id]--;

reverse(t);

}

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

printf("%d\n",res[i]);

return 0;

}

分块略大一些似乎会比较快。。

« 「BZOJ3781」小B的询问 WC2013糖果公园 »

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

「BZOJ3757」苹果树

Description

Input

Output

Sample Input

Sample Output

HINT

分类目录

热门文章

Myfriends

近期评论