「BZOJ4034」[HAOI2015] T2

2015年4月30日8,9572

Description

有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个

操作，分为三种：

操作 1 ：把某个节点 x 的点权增加 a 。

操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。

操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。

Input

第一行包含两个整数 N, M 。表示点数和操作数。

接下来一行 N 个整数，表示树中节点的初始权值。

接下来 N-1 行每行三个正整数 fr, to ，表示该树中存在一条边 (fr, to) 。

再接下来 M 行，每行分别表示一次操作。其中第一个数表示该操

作的种类（ 1-3 ），之后接这个操作的参数（ x 或者 x a ）。

Output

对于每个询问操作，输出该询问的答案。答案之间用换行隔开。

Sample Input

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

Sample Output

6
9
13

HINT

对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不

会超过 10^6 。

题解

树链剖分。。。

lca都不用求

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define mod 1000000000
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,cnt;
int last[100005];
int id,pos[100005],mx[100005],v[100005];
int bl[100005],size[100005],fa[100005];
ll tag[400005],sum[400005];
struct edge{
	int to,next;
}e[200005];
void insert(int u,int v)
{
	e[++cnt]=(edge){v,last[u]};last[u]=cnt;
	e[++cnt]=(edge){u,last[v]};last[v]=cnt;
}
void dfs(int x)
{
	size[x]=1;
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa[x])
		{
			fa[e[i].to]=x;
			dfs(e[i].to);
			size[x]+=size[e[i].to];
			mx[x]=max(mx[x],mx[e[i].to]);
		}
}
void dfs2(int x,int cha)
{
	bl[x]=cha;pos[x]=mx[x]=++id;
	int k=0;
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa[x]&&size[e[i].to]>size[k])
			k=e[i].to;
	if(k)
	{
		dfs2(k,cha);mx[x]=max(mx[x],mx[k]);
	}
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa[x]&&e[i].to!=k)
		{
			dfs2(e[i].to,e[i].to);
			mx[x]=max(mx[x],mx[e[i].to]);
		}
}
void pushdown(int l,int r,int k)
{
	if(l==r)return;
	int mid=(l+r)>>1;ll t=tag[k];tag[k]=0;
	tag[k<<1]+=t;tag[k<<1|1]+=t;
	sum[k<<1]+=t*(mid-l+1);
	sum[k<<1|1]+=t*(r-mid);
}
void add(int k,int l,int r,int x,int y,ll val)
{
	if(tag[k])pushdown(l,r,k);
	if(l==x&&y==r){tag[k]+=val;sum[k]+=(r-l+1)*val;return;}
	int mid=(l+r)>>1;
	if(x<=mid)add(k<<1,l,mid,x,min(mid,y),val);
	if(y>=mid+1)add(k<<1|1,mid+1,r,max(mid+1,x),y,val);
	sum[k]=sum[k<<1]+sum[k<<1|1];
}
ll query(int k,int l,int r,int x,int y)
{
	if(tag[k])pushdown(l,r,k);
	if(l==x&&y==r)return sum[k];
	int mid=(l+r)>>1;
	ll ans=0;
	if(x<=mid)
		ans+=query(k<<1,l,mid,x,min(mid,y));
	if(y>=mid+1)
		ans+=query(k<<1|1,mid+1,r,max(mid+1,x),y);
	return ans;
}
ll query(int x)
{
	ll ans=0;
	while(bl[x]!=1)
	{
		ans+=query(1,1,n,pos[bl[x]],pos[x]);
		x=fa[bl[x]];
	}
	ans+=query(1,1,n,1,pos[x]);
	return ans;
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)v[i]=read();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read();
		insert(u,v);
	}
	dfs(1);
	dfs2(1,1);
	for(int i=1;i<=n;i++)
		add(1,1,n,pos[i],pos[i],v[i]);
	int opt,x,a;
	while(m--)
	{
		opt=read();x=read();
		if(opt==1)
		{
			a=read();add(1,1,n,pos[x],pos[x],a);
		}
		if(opt==2)
		{
			a=read();add(1,1,n,pos[x],mx[x],a);
		}
		if(opt==3)printf("%lld\n",query(x));
	}
	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

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

#define mod 1000000000

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,cnt;

int last[100005];

int id,pos[100005],mx[100005],v[100005];

int bl[100005],size[100005],fa[100005];

ll tag[400005],sum[400005];

struct edge{

int to,next;

}e[200005];

void insert(int u,int v)

{

e[++cnt]=(edge){v,last[u]};last[u]=cnt;

e[++cnt]=(edge){u,last[v]};last[v]=cnt;

}

void dfs(int x)

{

size[x]=1;

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

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

{

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

dfs(e[i].to);

size[x]+=size[e[i].to];

mx[x]=max(mx[x],mx[e[i].to]);

}

void dfs2(int x,int cha)

{

bl[x]=cha;pos[x]=mx[x]=++id;

int k=0;

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

if(e[i].to!=fa[x]&&size[e[i].to]>size[k])

k=e[i].to;

if(k)

{

dfs2(k,cha);mx[x]=max(mx[x],mx[k]);

}

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

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

{

dfs2(e[i].to,e[i].to);

mx[x]=max(mx[x],mx[e[i].to]);

}

void pushdown(int l,int r,int k)

{

if(l==r)return;

int mid=(l+r)>>1;ll t=tag[k];tag[k]=0;

tag[k<<1]+=t;tag[k<<1|1]+=t;

sum[k<<1]+=t*(mid-l+1);

sum[k<<1|1]+=t*(r-mid);

}

void add(int k,int l,int r,int x,int y,ll val)

{

if(tag[k])pushdown(l,r,k);

if(l==x&&y==r){tag[k]+=val;sum[k]+=(r-l+1)*val;return;}

int mid=(l+r)>>1;

if(x<=mid)add(k<<1,l,mid,x,min(mid,y),val);

if(y>=mid+1)add(k<<1|1,mid+1,r,max(mid+1,x),y,val);

sum[k]=sum[k<<1]+sum[k<<1|1];

}

ll query(int k,int l,int r,int x,int y)

{

if(tag[k])pushdown(l,r,k);

if(l==x&&y==r)return sum[k];

int mid=(l+r)>>1;

ll ans=0;

if(x<=mid)

ans+=query(k<<1,l,mid,x,min(mid,y));

if(y>=mid+1)

ans+=query(k<<1|1,mid+1,r,max(mid+1,x),y);

return ans;

}

ll query(int x)

{

ll ans=0;

while(bl[x]!=1)

{

ans+=query(1,1,n,pos[bl[x]],pos[x]);

x=fa[bl[x]];

}

ans+=query(1,1,n,1,pos[x]);

return ans;

}

int main()

{

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

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

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

{

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

insert(u,v);

}

dfs(1);

dfs2(1,1);

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

add(1,1,n,pos[i],pos[i],v[i]);

int opt,x,a;

while(m--)

{

opt=read();x=read();

if(opt==1)

{

a=read();add(1,1,n,pos[x],pos[x],a);

}

if(opt==2)

{

a=read();add(1,1,n,pos[x],mx[x],a);

}

if(opt==3)printf("%lld\n",query(x));

}

return 0;

}

« 「BZOJ1513」[POI2006] Tet – Tetris 3D 「JoyOI」五月有奖赛暨Loi 55 Round #1 Day1 »

OIER

学长知道今年暑假NOI的具体日期么？

hzwer

没听说

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

「BZOJ4034」[HAOI2015] T2

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论