ACM-ICPC 2018 Jiaozuo Cyber ​​Preliminaries Jiu Yuan Wants to Eat - Tree Linking

You ye Jiu yuan is the daughter of the Great GOD Emancipator. And when she becomes an adult, she will be queen of Tusikur, so she wanted to travel the world while she was still young. In a country, she found a small pub called Whitehouse. Just as she was about to go in for a drink, the boss Carola appeared. And ask her to solve this problem or she will not be allowed to enter the pub. The problem description is as follows: There is a tree with nn n nodes, each node ii i contains weight a[i]a[i] a[i], the initial value of a[i]a[i] a[i] is 00 0. The root number of the tree is 11 1. Now you need to do the following operations: 1)1) 1) Multiply all weight on the path from uu u to vv v by xx x 2)2) 2) For all weight on the path from uu u to vv v, increasing xx x to them 3)3) 3) For all weight on the path from uu u to vv v, change them to the bitwise NOT of them 4)4) 4) Ask the sum of the weight on the path from uu u to vv v The answer modulo 2642^{64} 2 64 . Jiu Yuan is a clever girl, but she was not good at algorithm, so she hopes that you can help her solve this problem. Ding ∽∽∽\backsim\backsim\backsim ∽∽∽ The bitwise NOT is a unary operation that performs logical negation on each bit, forming the ones’ complement of the given binary value. Bits that are 00 0 become 11 1, and those that are 11 1 become 00 0. For example: NOT 0111 (decimal 7) = 1000 (decimal 8) NOT 10101011 = 01010100 Input The input contains multiple groups of data. For each group of data, the first line contains a number of nn n, and the number of nodes. The second line contains (n−1)(n - 1) (n−1) integers bib_i b i ​

, which means that the father node of node (i+1)(i +1) (i+1) is bib_i b i ​

. The third line contains one integer Mm m, which means the number of operations, The next Mm m lines contain the following four operations: At first, we input one integer opt 1) 1) 1) If opt is 11 1, then input 33 3 integers, u,v,xu, v, x u,v,x, which means multiply all weight on the path from Uu u to Vv v by Xx x 2) 2) 2) If opt is twenty two 2, then input 33 3 integers, u,v,xu, v, x u,v,x, which means for all weight on the path from Uu u to Vv v, increasing Xx x to them 3) 3) 3) If opt is 33 3, then input twenty two 2 integers, u,vu, v u,v, which means for all weight on the path from Uu u to Vv v, change them to the bitwise NOT of them 4) 4) 4) If opt is 44 4, then input twenty two 2 integers, u,vu, v u,v, and ask the sum of the weights on the path from Uu u to Vv v 1≤n,m,u,v≤1051 \le n,m,u,v \le 10^5 1≤n,m,u,v≤10 5 1≤x<2641 \le x < 2^{64} 1≤x<2 64 Output For each operation 44 4, output the answer. Sample input Copy 7 1 1 1 2 2 4 5 2 5 6 1 1 1 6 2 4 5 6 3 5 2 4 2 2 2 1 4 3 1 2 4 1 2 3 1 1 4 1 1 Sample output Copy 5 18446744073709551613 18446744073709551614 0 At first glance, it was a tree chain split, but I didn't know how to write it at the time. Later, I saw someone else's blog and found that it was a simple retreat, but my title was wrong. The bit is 2641x2641x, how is this -x, because he is mod264264 is the automatic modulo of unsigned long long, so -x becomes || |, then it becomes (264xx)%264(264xx)%264,那么就变成2641+(2641)x2641+(2641)x, you can use the addition and multiplication to save, there is a little obvious knowledge to know: val*(x+B)=val*x+val*B, so addf The array is also multiplied by val.

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
ll inf=18446744073709551615;
const int maxn=2e5+5;
struct node
{
    int to,next;
}e[maxn*2];
int head[maxn],cnt,tim,fa[maxn],son[maxn],dep[maxn],top[maxn],en[maxn],siz[maxn],pos[maxn];
ll mulf[maxn*4],addf[maxn*4],sum[maxn*4],a[maxn];
int n,m,rt;
void add(int x,int y)
{
    e[cnt].to=y;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
void dfs1(int u)
{
    siz[u]=1;
    for (int i=head[u];~i;i=e[i].next)
    {
        int v=e[i].to;
        if (v!=fa[u])
        {
            fa[v]=u;
            dep[v]=dep[u]+1;
            dfs1(v);
            siz[u]+=siz[v];
            if (son[u]==0||siz[v]>siz[son[u]])
                son[u]=v;
        }
    }
}
void dfs2(int u,int f)
{
    tim++;
    top[u]=f;
    pos[u]=tim;
    if (son[u]) dfs2(son[u],f);
    for (int i=head[u];~i;i=e[i].next)
    {
        int v=e[i].to;
        if (v!=fa[u]&&v!=son[u])
        {
            dfs2(v,v);
        }
    }
    en[u]=tim;
}
void pushup(int root)
{
    sum[root]=sum[root<<1]+sum[root<<1|1];
}
void pushdown(int l,int r,int root)
{
    int mid=l+r>>1;
    sum[root<<1]=sum[root<<1]*mulf[root]+addf[root]*(mid-l+1);
    sum[root<<1|1]=sum[root<<1|1]*mulf[root]+addf[root]*(r-mid);
    mulf[root<<1]=mulf[root<<1]*mulf[root];
    mulf[root<<1|1]=mulf[root<<1|1]*mulf[root];
    addf[root<<1]=addf[root<<1]*mulf[root]+addf[root];
    addf[root<<1|1]=addf[root<<1|1]*mulf[root]+addf[root];
    addf[root]=0;
    mulf[root]=1;
}
void add(int l,int r,int root,int ql,int qr,ll val,int op)
{
    if(l>=ql&&r<=qr)
    {
        if(op==1)
        {
            mulf[root]*=val;
            sum[root]*=val;
            addf[root]*=val;
        }
        else if(op==2)
        {
            sum[root]+=(r-l+1)*val;
            addf[root]+=val;
        }
        else
        {
            sum[root]=inf*sum[root]+(r-l+1)*inf;
            addf[root]=inf*addf[root]+inf;
            mulf[root]*=inf;
        }
        return ;
    }
    pushdown(l,r,root);
    int mid=l+r>>1;
    if(mid>=ql)
        add(l,mid,root<<1,ql,qr,val,op);
    if(mid<qr)
        add(mid+1,r,root<<1|1,ql,qr,val,op);
    pushup(root);
}
ll ask(int l,int r,int root,int ql,int qr)
{
    if(l>=ql&&r<=qr)
        return sum[root];
    int mid=l+r>>1;
    pushdown(l,r,root);
    ll ans=0;
    if(mid>=ql)
        ans+=ask(l,mid,root<<1,ql,qr);
    if(mid<qr)
        ans+=ask(mid+1,r,root<<1|1,ql,qr);
    return ans;
}
void update(int x,int y,ll val,int op)
{
    while (top[x]!=top[y])
    {
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        add(1,n,1,pos[top[x]],pos[x],val,op);
        x=fa[top[x]];
    }
    if (pos[x]>pos[y]) swap(x,y);
    add(1,n,1,pos[x],pos[y],val,op);
}
void query(int x,int y)
{
    ll ans=0;
    while (top[x]!=top[y])
    {
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        ans+=ask(1,n,1,pos[top[x]],pos[x]);
        x=fa[top[x]];
    }
    if (pos[x]>pos[y]) swap(x,y);
    ans+=ask(1,n,1,pos[x],pos[y]);
    printf("%llu\n",ans);
}
int main()
{
    while(~scanf("%d",&n))
    {
        memset(head,-1,sizeof(head));
        for(int i=0;i<maxn;i++)
            fa[i]=son[i]=dep[i]=top[i]=siz[i]=pos[i]=0;
        cnt=tim=0;
        for(int i=0;i<maxn*4;i++)
            mulf[i]=1,addf[i]=sum[i]=0;
        int sta,fin;
        ll val;
        for(int i=2;i<=n;i++)
        {
            scanf("%d",&sta);
            add(sta,i),add(i,sta);
        }
        rt=1;
        dfs1(rt);
        dfs2(rt,rt);
        int op;
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&op);
            if(op==1)
            {
                scanf("%d%d%llu",&sta,&fin,&val);
                update(sta,fin,val,op);
            }
            else if(op==2)
            {
                scanf("%d%d%llu",&sta,&fin,&val);
                update(sta,fin,val,op);
            }
            else if(op==3)
            {
                scanf("%d%d",&sta,&fin);
                update(sta,fin,0,op);

            }
            else
            {
                scanf("%d%d",&sta,&fin);
                query(sta,fin);
            }
        }
    }

    return 0;
}