WC2013糖果公园

2014年11月29日9,0475

Description

Input

Output

Sample Input

Sample Output

84
131
27
84

HINT

题解

30分暴力。。。模拟即可

第4-5个测试点由于m较小，且在链上，所以可以用前缀和水过。。。

对于每个询问统计每种糖果的答案贡献

满分做法带修改树上莫队。。。

参见vfk的博客

http://vfleaking.blog.163.com/blog/#m=0&t=1&c=fks_084070093085082071086081080095085081085075084081080064080

但是vfk的这种树分块方式。。。

。。。感觉[B,3B]的话把应该把B设小点，但是这样的话链上就会。。。

不过这些都无所谓啦。。。

#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;
int read()
{
    int 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;
}
int n,m,q,cnt;
int tim[10005];
ll V[10005],W[10005],C[10005];
int last[10005],fa[10005],deep[10005];
struct edge{int to,next;}e[20005];
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 dp(int x)
{
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa[x])
		{
			deep[e[i].to]=deep[x]+1;
			fa[e[i].to]=x;
			dp(e[i].to);
		}
}
void query(int x,int y)
{
	ll ans=0;
	memset(tim,0,sizeof(tim));
	while(x!=y)
	{
		if(deep[x]<deep[y])ans+=V[C[y]]*W[++tim[C[y]]],y=fa[y];
		else ans+=V[C[x]]*W[++tim[C[x]]],x=fa[x];
	}
	ans+=V[C[x]]*W[++tim[C[x]]];
	printf("%lld\n",ans);
}
int main()
{
	n=read();m=read();q=read();
	for(int i=1;i<=m;i++)V[i]=read();
	for(int i=1;i<=n;i++)W[i]=read();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read();
		insert(u,v);
	}
	dp(1);
	for(int i=1;i<=n;i++)C[i]=read();
	for(int i=1;i<=q;i++)
	{
		int typ=read(),x=read(),y=read();
		if(!typ)
			C[x]=y;
		else query(x,y);
	}
	return 0;
}

#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;

int read()

{

int 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;

}

int n,m,q,cnt;

int tim[10005];

ll V[10005],W[10005],C[10005];

int last[10005],fa[10005],deep[10005];

struct edge{int to,next;}e[20005];

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 dp(int x)

{

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

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

{

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

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

dp(e[i].to);

}

void query(int x,int y)

{

ll ans=0;

memset(tim,0,sizeof(tim));

while(x!=y)

{

if(deep[x]<deep[y])ans+=V[C[y]]*W[++tim[C[y]]],y=fa[y];

else ans+=V[C[x]]*W[++tim[C[x]]],x=fa[x];

}

ans+=V[C[x]]*W[++tim[C[x]]];

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

}

int main()

{

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

for(int i=1;i<=m;i++)V[i]=read();

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

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

{

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

insert(u,v);

}

dp(1);

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

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

{

int typ=read(),x=read(),y=read();

if(!typ)

C[x]=y;

else query(x,y);

}

return 0;

}

#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;
int read()
{
    int 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;
}
int n,m,Q,tot,cnt;;
ll V[100005],W[100005],C[100005],sum[100005];
int q[100005],pos[100005],d[100005];
int S[105][100005];
int last[100005];
struct edge{int to,next;}e[200005];
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;
	d[u]++;d[v]++;
}
void dfs(int x,int f)
{
	pos[x]=++tot;
	q[tot]=x;
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=f)
			dfs(e[i].to,x);
}
void query(int x,int y)
{
	if(x>y)swap(x,y);
	ll ans=0;
	for(int i=1;i<=m;i++)
		ans+=sum[S[i][y]-S[i][x-1]]*V[i];
	printf("%lld\n",ans);
}
int main()
{
	n=read();m=read();Q=read();
	for(int i=1;i<=m;i++)V[i]=read();
	for(int i=1;i<=n;i++)W[i]=read();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read();
		insert(u,v);
	}
	for(int i=1;i<=n;i++)
		if(d[i]==1){dfs(i,0);break;}
	for(int i=1;i<=n;i++)C[i]=read();
	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+W[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			S[j][i]=S[j][i-1];
		S[C[q[i]]][i]++;
	}
	for(int i=1;i<=Q;i++)
	{
		int typ=read(),x=read(),y=read();
	    query(pos[x],pos[y]);
	}
	return 0;
}

#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;

int read()

{

int 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;

}

int n,m,Q,tot,cnt;;

ll V[100005],W[100005],C[100005],sum[100005];

int q[100005],pos[100005],d[100005];

int S[105][100005];

int last[100005];

struct edge{int to,next;}e[200005];

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;

d[u]++;d[v]++;

}

void dfs(int x,int f)

{

pos[x]=++tot;

q[tot]=x;

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

if(e[i].to!=f)

dfs(e[i].to,x);

}

void query(int x,int y)

{

if(x>y)swap(x,y);

ll ans=0;

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

ans+=sum[S[i][y]-S[i][x-1]]*V[i];

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

}

int main()

{

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

for(int i=1;i<=m;i++)V[i]=read();

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

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

{

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

insert(u,v);

}

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

if(d[i]==1){dfs(i,0);break;}

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

for(int i=1;i<=n;i++)sum[i]=sum[i-1]+W[i];

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

{

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

S[j][i]=S[j][i-1];

S[C[q[i]]][i]++;

}

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

{

int typ=read(),x=read(),y=read();

query(pos[x],pos[y]);

}

return 0;

}

100

#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;
int read()
{
    int 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 ans,res[100005];
int bin[20];
int n,m,Q,ind,cnt,top;
int blo,blonum;
ll V[100005],W[100005],C[100005],pre[100005];
int fa[100005][17];
int last[100005],q[100005],deep[100005],belong[100005],dfn[100005];
int num[100005];
bool vis[100005];
struct edge{int to,next;}e[200005];
struct query{int x,y,t,id;}b[100005];
struct change{int x,y,t,pre;}c[100005];
bool operator<(query a,query b)
{
	if(belong[a.x]==belong[b.x]&&belong[a.y]==belong[b.y])return a.t<b.t;
	else if(belong[a.x]==belong[b.x])return belong[a.y]<belong[b.y];
	else return belong[a.x]<belong[b.x];
}
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[q[top--]]=blonum;
				size=0;
			}
		}
	q[++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(bin[i]&t)
			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])ans-=W[num[C[x]]]*V[C[x]],num[C[x]]--;
	else num[C[x]]++,ans+=W[num[C[x]]]*V[C[x]];
	vis[x]^=1;
}
void change(int x,int y)
{
	if(vis[x])
	{
		reverse(x);
		C[x]=y;
		reverse(x);
	}
	else C[x]=y;
}
void solve(int x,int y)
{
	while(x!=y)
	{
		if(deep[x]>deep[y])reverse(x),x=fa[x][0];
		else reverse(y),y=fa[y][0];
	}
}
int main()
{
	bin[0]=1;
	for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;
	n=read();m=read();Q=read();
	blo=pow(n,2.0/3)*0.5;
	for(int i=1;i<=m;i++)V[i]=read();
	for(int i=1;i<=n;i++)W[i]=read();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read();
		insert(u,v);
	}
	for(int i=1;i<=n;i++)pre[i]=C[i]=read();
	dfs(1);
	while(top)belong[q[top--]]=blonum;
	int c1=0,c2=0;
  	for(int i=1;i<=Q;i++)
	{
		int typ=read(),x=read(),y=read();
		if(!typ)
		{
			c1++;
			c[c1].x=x;c[c1].y=y;c[c1].pre=pre[x];pre[x]=y;
		}
		else 
		{
			c2++;
			if(dfn[x]>dfn[y])swap(x,y);
			b[c2].x=x;b[c2].y=y;b[c2].id=c2;b[c2].t=c1;
		}
	}
	sort(b+1,b+c2+1);
	for(int i=1;i<=b[1].t;i++)
		change(c[i].x,c[i].y);
	solve(b[1].x,b[1].y);
	int t=lca(b[1].x,b[1].y);
	reverse(t);res[b[1].id]=ans;reverse(t);
	for(int i=2;i<=c2;i++)
	{
		for(int j=b[i-1].t+1;j<=b[i].t;j++)
			change(c[j].x,c[j].y);
		for(int j=b[i-1].t;j>b[i].t;j--)
			change(c[j].x,c[j].pre);
		solve(b[i-1].x,b[i].x);
		solve(b[i-1].y,b[i].y);
		int t=lca(b[i].x,b[i].y);
		reverse(t);res[b[i].id]=ans;reverse(t);
	}
	for(int i=1;i<=c2;i++)
		printf("%lld\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

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

#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;

int read()

{

int 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 ans,res[100005];

int bin[20];

int n,m,Q,ind,cnt,top;

int blo,blonum;

ll V[100005],W[100005],C[100005],pre[100005];

int fa[100005][17];

int last[100005],q[100005],deep[100005],belong[100005],dfn[100005];

int num[100005];

bool vis[100005];

struct edge{int to,next;}e[200005];

struct query{int x,y,t,id;}b[100005];

struct change{int x,y,t,pre;}c[100005];

bool operator<(query a,query b)

{

if(belong[a.x]==belong[b.x]&&belong[a.y]==belong[b.y])return a.t<b.t;

else if(belong[a.x]==belong[b.x])return belong[a.y]<belong[b.y];

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

}

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[q[top--]]=blonum;

size=0;

}

q[++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(bin[i]&t)

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])ans-=W[num[C[x]]]*V[C[x]],num[C[x]]--;

else num[C[x]]++,ans+=W[num[C[x]]]*V[C[x]];

vis[x]^=1;

}

void change(int x,int y)

{

if(vis[x])

{

reverse(x);

C[x]=y;

reverse(x);

}

else C[x]=y;

}

void solve(int x,int y)

{

while(x!=y)

{

if(deep[x]>deep[y])reverse(x),x=fa[x][0];

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

}

int main()

{

bin[0]=1;

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

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

blo=pow(n,2.0/3)*0.5;

for(int i=1;i<=m;i++)V[i]=read();

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

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

{

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

insert(u,v);

}

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

dfs(1);

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

int c1=0,c2=0;

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

{

int typ=read(),x=read(),y=read();

if(!typ)

{

c1++;

c[c1].x=x;c[c1].y=y;c[c1].pre=pre[x];pre[x]=y;

}

else

{

c2++;

if(dfn[x]>dfn[y])swap(x,y);

b[c2].x=x;b[c2].y=y;b[c2].id=c2;b[c2].t=c1;

}

sort(b+1,b+c2+1);

for(int i=1;i<=b[1].t;i++)

change(c[i].x,c[i].y);

solve(b[1].x,b[1].y);

int t=lca(b[1].x,b[1].y);

reverse(t);res[b[1].id]=ans;reverse(t);

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

{

for(int j=b[i-1].t+1;j<=b[i].t;j++)

change(c[j].x,c[j].y);

for(int j=b[i-1].t;j>b[i].t;j--)

change(c[j].x,c[j].pre);

solve(b[i-1].x,b[i].x);

solve(b[i-1].y,b[i].y);

int t=lca(b[i].x,b[i].y);

reverse(t);res[b[i].id]=ans;reverse(t);

}

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

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

return 0;

}

« 「BZOJ3757」苹果树「BZOJ3289」Mato的文件管理 »

涨红

黄学长请问能不能证明一下时间复杂度
感觉加上一维时间每次修改可以到O（n）
不太靠谱。。

hzwer

vfk的博客里有，n^(5/3)的复杂度，类似一般莫队的分析

逗比

吃个饭就懂了……

SkyDec

这题要注意常数，不然会像我一样疯狂地爆OJ

hzwer

嘿嘿嘿我有数据

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

WC2013糖果公园

Description

Input

Output

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论