谁看看树剖为什么RE了

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <cctype>
#include <ctime>
#define INF (1<<29)
#define N 210000
using namespace std;

void read(int &k)
{
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();}
k=x*f;
}

int n,Q,nn,inde,root;
int fa[N],p[N],size[N],top[N],tree[N],deep[N],son[N],a[N],numdeep[N],ftree[N];

struct edge
{
int a,b,nt;
}e[1000010];

struct segtree
{
int l,r,val;
}seg[N*4];

void anode(int x,int y)
{
nn++;e[nn].a=x;e[nn].b=y;e[nn].nt=p[x];p[x]=nn;
nn++;e[nn].a=y;e[nn].b=x;e[nn].nt=p[y];p[y]=nn;
}

void dfs1(int x,int d)
{
size[x]=1;deep[x]=d;
for(int i=p[x];i;i=e[i].nt)
{
int v=e[i].b;
if(v==fa[x]) continue;
fa[v]=x;
dfs1(v,d+1);
size[x]+=size[v];
if(size[v]>size[son[x]])
son[x]=v;
}
}

void dfs2(int x,int chain)
{
top[x]=chain,tree[x]=++inde;
ftree[tree[x]]=x;
if(!son[x]) return ;
dfs2(son[x],chain);
for(int i=p[x];i;i=e[i].nt)
{
int v=e[i].b;
if(v!=fa[x]&&v!=son[x])
dfs2(v,v);
}
}

void pushup(int k)
{
seg[k].val=seg[k<<1].val+seg[k<<1|1].val;
}

void build(int k,int l,int r)
{
seg[k].l=l,seg[k].r=r;
int mid=(l+r)/2;
if(l==r)
{
if(deep[ftree[l]]%2==1)
seg[k].val=a[ftree[l]];
else
seg[k].val=-a[ftree[l]];
return ;
}

build(k<<1,l,mid),build(k<<1|1,mid+1,r);
pushup(k);
}

void update(int k,int pos,int val)
{
int mid=(seg[k].l+seg[k].r)/2;
if(seg[k].l==pos&&seg[k].r==pos)
{
seg[k].val+=val;
return ;
}
if(pos<=mid) update(k<<1,pos,val);
else update(k<<1|1,pos,val);
pushup(k);
}

int query(int k,int l,int r)
{
int mid=(seg[k].l+seg[k].r)/2;
if(seg[k].l==l&&seg[k].r==r)
return seg[k].val;
if(r<=mid) return query(k<<1,l,r);
else if(l>mid) return query(k<<1|1,l,r);
else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);
}

int solvequery(int x,int y)
{
int rnt=0;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
rnt+=query(1,tree[top[x]],tree[x]);
x=fa[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
rnt+=query(1,tree[x],tree[y]);
return rnt;
}

int main()
{
//freopen("D:\code\in.txt","r",stdin);
read(n),read(Q);
for(int i=1;i<=n;i++)
read(a[i]);
for(int x,i=1;i<=n;i++)
{
read(x);
if(x==-1)
{
root=i;
continue;
}
anode(i,x);
}
deep[root]=1;fa[root]=-1;
dfs1(root,1),dfs2(root,1);
for(int i=1;i<=n;i++)
numdeep[deep[i]]++;
build(1,1,n);
while(Q--)
{
char s[2];
int x,y;
scanf("%s%d%d",s,&x,&y);
if(s[0]=='M')
{
if(x%2==0) y=-y;
for(int cnt=0,i=1;i<=n;i++)
{
if(cnt==numdeep[x])
break;
if(deep[i]==x)
cnt++,update(1,tree[i],y);
}
}
else
printf("%d\n",abs(solvequery(x,y)));
}
return 0;
}

2 条评论

  • 1

信息

ID
1710
难度
7
分类
树结构 | 树结构 | 最近公共祖先数据结构 | 树状数组 点击显示
标签
(无)
递交数
808
已通过
150
通过率
19%
被复制
7
上传者