[搬家]树链剖分.最后一题 BZOJ 4034
希望这题不要变成权限题...
有点害怕= =
算法:树链剖分
数组开小啦RE啦.....
cout被卡出RE啦.....
题目如下:
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
9
13
代码如下:
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[100005];
struct edge
{
int y;
edge * next;
};
edge * li[100005];
edge * new_edge()
{
static edge a[200005];
static int top=0;
return &a[top++];
}
void inserts(int x,int y)
{
edge * t=new_edge();
t->y=y;
t->next=li[x];
li[x]=t;
}
void insert_edge(int x,int y)
{
inserts(x,y);
inserts(y,x);
}
edge * hev_ch[1000005];
int father[100005];
int size[100005];
int up[100005];
void dfs1(int x)
{
edge * t;
int max_val=0;
size[x]=1;
for (t=li[x];t!=0;t=t->next)
{
if (t->y==father[x]) continue;
father[t->y]=x;
dfs1(t->y);
size[x]+=size[t->y];
if (size[t->y]>max_val)
{
max_val=size[t->y];
hev_ch[x]=t;
}
}
}
int dfn[100005];
int vis[100005];
void dfs2(int x)
{
static int now=0;
dfn[x]=now;
vis[now]=x;
now++;
if (hev_ch[x]==0) return;
up[hev_ch[x]->y]=up[x];
dfs2(hev_ch[x]->y);
edge * t;
for (t=li[x];t!=0;t=t->next)
{
if (t->y==father[x]) continue;
if (t==hev_ch[x]) continue;
up[t->y]=t->y;
dfs2(t->y);
}
}
long long val[1<<18],tag[1<<18];
void push_down(int num,int l,int r)
{
if (tag[num]==0) return;
int mid=(l+r)>>1;
val[num*2+1]+=(mid-l)*tag[num];
val[num*2+2]+=(r-mid)*tag[num];
tag[num*2+1]+=tag[num];
tag[num*2+2]+=tag[num];
tag[num]=0;
}
void build_tree(int num,int l,int r)
{
if (l==r-1)
{
val[num]=a[vis[l]];
return;
}
int mid=(l+r)/2;
build_tree(num*2+1,l,mid);
build_tree(num*2+2,mid,r);
val[num]=val[num*2+1]+val[num*2+2];
}
long long query(int num,int l,int r,int l0,int r0)
{
if ((l0<=l)&&(r<=r0))
{
return val[num];
}
int mid=(l+r)/2;
push_down(num,l,r);
long long ans=0;
if (l0<mid) ans+=query(num*2+1,l,mid,l0,r0);
if (mid<r0) ans+=query(num*2+2,mid,r,l0,r0);
return ans;
}
void change1(int num,int l,int r,int k,int t)
{
if (l==r-1)
{
val[num]+=t;
return;
}
push_down(num,l,r);
int mid=(l+r)/2;
if (k<mid)
{
change1(num*2+1,l,mid,k,t);
}
else
{
change1(num*2+2,mid,r,k,t);
}
val[num]=val[num*2+1]+val[num*2+2];
}
void change2(int num,int l,int r,int l0,int r0,int t)
{
if ((l0<=l)&&(r<=r0))
{
val[num]+=(long long)t*(r-l);
tag[num]+=t;
return;
}
push_down(num,l,r);
int mid=(l+r)/2;
if (l0<mid) change2(num*2+1,l,mid,l0,r0,t);
if (mid<r0) change2(num*2+2,mid,r,l0,r0,t);
val[num]=val[num*2+1]+val[num*2+2];
}
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
ios::sync_with_stdio(false);
int n,m;
scanf("%d%d",&n,&m);
int i;
for (i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for (i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
x--;
y--;
insert_edge(x,y);
}
father[0]=-1;
up[0]=0;
dfs1(0);
dfs2(0);
build_tree(0,0,n);
for (i=0;i<m;i++)
{
int oper;
scanf("%d",&oper);
if (oper==1)
{
int x,y;
scanf("%d%d",&x,&y);
x--;
change1(0,0,n,dfn[x],y);
}
else if (oper==2)
{
int x,y;
scanf("%d%d",&x,&y);
x--;
change2(0,0,n,dfn[x],dfn[x]+size[x],y);
}
else
{
int x;
scanf("%d",&x);
x--;
long long sum=0;
for (;x!=-1;)
{
sum+=query(0,0,n,dfn[up[x]],dfn[x]+1);
x=father[up[x]];
}
cout<<sum<<'\n';
}
}
return 0;
}
评论 (0)