# ACM-ICPC 2018 race area network preliminaries E (tree chain split + line segment tree)

Topic: Give you a tree, the root node is 1, the initial value of each node is 0, support the following operations

1. u v x multiplies the value of each node on the U - > V path by X

2. u v x adds x to every node value on U - > V path

3. u v reverses the value of each node on the U - > V path bit by bit

4. u v Finds the sum of the values of each node on the U - > V path

Analysis: If there is no 3 operations, it is a naked tree dissection problem, but 3 can be obtained by combining addition and multiplication, and X is inverse = all 1 (64 1)-X.

That is to say, the value of X*(-1)+the maximum unsigned long will actually overflow naturally by taking 2 ^ 64 modules.

Ac code:

```#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull ULLmax=18446744073709551615;
const int maxn=1e5+5;
/// Tree section
int dfn[maxn],dep[maxn],sze[maxn],rk[maxn],son[maxn],fa[maxn],top[maxn];
struct Edge{
int v,nxt;
}edge[maxn<<1];
void init(int n)
{
tot=0;
cnt=0;/// dfs serial node number
for(int i=0;i<=n;i++) sze[i]=0,dep[i]=0,son[i]=0,dfn[i]=0,rk[i]=0,fa[i]=0,top[i]=0;
dep[1]=1;
}
{
edge[tot].v=v;
}
void dfs1(int u,int faa)
{
sze[u]=1;
{
int v=edge[i].v;
if(v==faa) continue;
dep[v]=dep[u]+1;
fa[v]=u;
dfs1(v,u);
sze[u]+=sze[v];
if(sze[v]>sze[son[u]])
son[u]=v;
}
}
void dfs2(int u,int Top)
{
dfn[u]=++cnt;
rk[cnt]=u;
top[u]=Top;
if(son[u]) dfs2(son[u],Top);
{
int v=edge[i].v;
if(v!=fa[u]&&v!=son[u])
dfs2(v,v);
}
}
/// Segment Tree Section
struct Tree{
ull sum,lazy1,lazy2;/// lazy 1 is plus and lazy 2 is multiplication
}tree[maxn<<2];
void pushup(int rt)
{
tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}
void pushdown(int rt,int llen,int rlen)
{
if(tree[rt].lazy2!=1)
{
tree[rt<<1].sum*=tree[rt].lazy2;
tree[rt<<1].lazy2*=tree[rt].lazy2;
tree[rt<<1].lazy1*=tree[rt].lazy2;

tree[rt<<1|1].sum*=tree[rt].lazy2;
tree[rt<<1|1].lazy2*=tree[rt].lazy2;
tree[rt<<1|1].lazy1*=tree[rt].lazy2;

tree[rt].lazy2=1;
}
if(tree[rt].lazy1)
{
tree[rt<<1].sum+=tree[rt].lazy1*llen;
tree[rt<<1].lazy1+=tree[rt].lazy1;

tree[rt<<1|1].sum+=tree[rt].lazy1*rlen;
tree[rt<<1|1].lazy1+=tree[rt].lazy1;
tree[rt].lazy1=0;
}
}
void buildtree(int rt,int l,int r)
{
if(l==r){
tree[rt].sum=0;
tree[rt].lazy1=0;
tree[rt].lazy2=1;
return;
}
int mid=(l+r)>>1;
pushdown(rt,mid-l+1,r-mid);/// Don't forget, to update the lazy tag, the default lazy is 0, and now lazy is 1.
buildtree(rt<<1,l,mid);
buildtree(rt<<1|1,mid+1,r);
pushup(rt);
}
void update1(int rt,int l,int r,int L,int R,ull val)//Plus
{
if(L<=l&&r<=R){
tree[rt].lazy1+=val;
tree[rt].sum+=val*(r-l+1);
return;
}
int mid=(l+r)>>1;
pushdown(rt,mid-l+1,r-mid);
if(mid>=L) update1(rt<<1,l,mid,L,R,val);
if(mid<R) update1(rt<<1|1,mid+1,r,L,R,val);
pushup(rt);
}
void update2(int rt,int l,int r,int L,int R,ull val)/// ride
{
if(L<=l&&r<=R){
tree[rt].lazy2*=val;
tree[rt].lazy1*=val;
tree[rt].sum*=val;
return;
}
int mid=(l+r)>>1;
pushdown(rt,mid-l+1,r-mid);
if(mid>=L) update2(rt<<1,l,mid,L,R,val);
if(mid<R) update2(rt<<1|1,mid+1,r,L,R,val);
pushup(rt);
}
ull query(int rt,int l,int r,int L,int R)
{
if(L<=l&&r<=R){
return tree[rt].sum;
}
int mid=(l+r)>>1;
ull ans=0;
pushdown(rt,mid-l+1,r-mid);
if(mid>=L) ans+=query(rt<<1,l,mid,L,R);
if(mid<R) ans+=query(rt<<1|1,mid+1,r,L,R);
return ans;
}
{
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]])
swap(u,v);
update1(1,1,n,dfn[top[u]],dfn[u],val);
u=fa[top[u]];
}
if(dep[u]<dep[v])
swap(u,v);
update1(1,1,n,dfn[v],dfn[u],val);
}
void upmul(int u,int v,ull val)
{
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]])
swap(u,v);
update2(1,1,n,dfn[top[u]],dfn[u],val);
u=fa[top[u]];
}
if(dep[u]<dep[v])
swap(u,v);
update2(1,1,n,dfn[v],dfn[u],val);
}
ull qsum(int u,int v)
{
ull ans=0;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]])
swap(u,v);
ans+=query(1,1,n,dfn[top[u]],dfn[u]);
u=fa[top[u]];
}
if(dep[u]<dep[v])
swap(u,v);
ans+=query(1,1,n,dfn[v],dfn[u]);
return ans;
}
int main()
{
int m,u,v;
while(scanf("%d",&n)!=EOF)
{
init(n);
for(int i=2;i<=n;i++)
{
scanf("%d",&u);
}
dfs1(1,-1);
dfs2(1,1);
buildtree(1,1,n);
scanf("%d",&m);
int op;
ull x;
while(m--){
scanf("%d%d%d",&op,&u,&v);
if(op==1){
scanf("%llu",&x);
upmul(u,v,x);
///updatemul();
}
else if(op==2){
scanf("%llu",&x);
}
else if(op==3){
upmul(u,v,-1);
}
else{
printf("%llu\n",qsum(u,v));
///query();
}
}
}
return 0;
}
```

Posted on Wed, 09 Oct 2019 12:04:56 -0700 by dupreelove