树上行走(牛客)
题目大意:
一棵树,两个操作
操作一:将x->y路径的每个点的b值加上前一个点的a值
操作二:查询一个点的b值
首先很容易想到树链剖分+树上差分,难点就是细节的处理
对向上向下两个方向的边分别用树状数组维护
#include
#define LL long long
#define pb push_back
using namespace std;
const int N=5e5+9;
int n,q,cnt;
int a[N],c[N][2],d[N],son[N],tp[N],f[N],dfn[N],sz[N];
LL ans[N];
vectore[N];
void dfs1(int x,int fa,int deep)
{
d[x]=deep; f[x]=fa; sz[x]=1;
int maxn=0;
for(int y:e[x])
{
if(y==fa) continue;
dfs1(y,x,deep+1);
sz[x]+=sz[y];
if(sz[y]>maxn) maxn=sz[y],son[x]=y;
}
}
void dfs2(int x,int top)
{
dfn[x]=++cnt; tp[x]=top;
if(!son[x]) return;
dfs2(son[x],top);
for(int y:e[x])
if(y!=f[x]&&y!=son[x])
dfs2(y,y);
}
int lowbit(int x)
{
return x&-x;
}
void Add(int x,int t,int v)
{
while(x<=n)
{
c[x][t]+=v;
x+=lowbit(x);
}
}
void update(int x,int y)
{
while(tp[x]!=tp[y])
{
if(d[tp[x]]>d[tp[y]])
{
Add(dfn[tp[x]],0,1);
Add(dfn[x],0,-1);
ans[f[tp[x]]]+=a[tp[x]];
x=f[tp[x]];
}
else
{
Add(dfn[tp[y]],1,1);
Add(dfn[y]+1,1,-1);
y=f[tp[y]];
}
}
if(d[x]>d[y])
{
Add(dfn[y],0,1);
Add(dfn[x],0,-1);
}
else
{
Add(dfn[x]+1,1,1);
Add(dfn[y]+1,1,-1);
}
}
int Sum(int x,int t)
{
int temp=0;
while(x)
{
temp+=c[x][t];
x-=lowbit(x);
}
return temp;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1,x,y;i>x>>y;
e[x].pb(y); e[y].pb(x);
}
dfs1(1,0,1);
dfs2(1,1);
while(q--)
{
int t,x,y;
cin>>t;
if(t==1)
{
cin>>x>>y;
update(x,y);
}
else
{
cin>>x;
cout<
相关