洛谷P3613 睡觉困难综合征

题目背景

刚立完Flag我就挂了WC和THUWC。。。

时间限制0.5s，空间限制128MB

因为Claris大佬帮助一周目由乃通过了Deus的题，所以一周目的由乃前往二周目世界找雪辉去了

由于二周目世界被破坏殆尽，所以由乃和雪辉天天都忙着重建世界（其实和MC差不多吧），Deus看到了题问她，总是被告知无可奉告

Deus没办法只能去三周目世界问三周目的由乃OI题。。。

三周目的世界中，因为没有未来日记，所以一切都很正常，由乃天天认真学习。。。

因为Deus天天问由乃OI题，所以由乃去学习了一下OI

由于由乃智商挺高，所以OI学的特别熟练

她在RBOI2016中以第一名的成绩进入省队，参加了NOI2016获得了金牌保送

Deus：这个题怎么做呀？

yuno：这个不是NOI2014的水题吗。。。

Deus：那如果出到树上，多组链询问，带修改呢？

yuno：诶。。。？？？

Deus：这题叫做睡觉困难综合征哟~

虽然由乃OI很好，但是她基本上不会DS，线段树都只会口胡，比如她NOI2016的分数就是100+100+100+0+100+100。。。NOIP2017的分数是100+0+100+100+0+100

所以她还是只能找你帮她做了。。。

题目描述

由乃这个问题越想越迷糊，已经达到了废寝忘食的地步。结果她发现……晚上睡不着了！只能把自己的一个神经元（我们可以抽象成一个树形结构）拿出来，交给Deus。

这个神经元是一个有n个点的树，每个点的包括一个位运算opt和一个权值x，位运算有&,l,^三种，分别用1,2,3表示。

为了治疗失眠，Deus可以将一些神经递质放在点x上，初始的刺激值是。然后v依次经过从x到y的所有节点，每经过一个点i，v就变成v opti xi，所以他想问你，最后到y时，希望得到的刺激值尽可能大，所以最大值的v可以是多少呢？当然由于初始的神经递质的量有限，所以给定的初始值必须是在[0,z]之间。Deus每次都会给你3个数，x,y,z。

不过，Deus为了提升治疗效果，可能会对一些神经节点进行微调。在这种情况下，也会给三个数x，y，z，意思是把x点的操作修改为y，数值改为z

输入输出格式

输入格式：

第一行三个数n，m，k。k的意义是每个点上的数，以及询问中的数值z都 $<

2^k$。之后n行，每行两个数x,y表示该点的位运算编号以及数值

之后n - 1行，每行两个数x,y表示x和y之间有边相连

之后m行，每行四个数，Q,x,y,z表示这次操作为Q(1位询问，2为更改)，x，y，z意义如题所述

输出格式：

对于每个操作1，输出到最后可以造成的最大刺激度v

输入输出样例

输入样例#1：

5 5 3
1 7
2 6
3 7
3 6
3 1
1 2
2 3
3 4
1 5
1 1 4 7
1 1 3 5
2 1 1 3
2 3 3 3
1 1 3 2

输出样例#1：

7
1
5

输入样例#2：

2 2 2
2 2
2 2
1 2
2 2 2 2
1 2 2 2

输出样例#2：

3

说明

对于30%的数据，n，m <= 1

对于另外20%的数据，k <= 5

对于另外20%的数据，位运算只会出现一种

对于100%的数据，0 <= n , m <= 100000 , k <= 64

树 LCT 位运算 贪心

略神的题。

基本的操作@NOI2014起床困难综合征

出到树上的话，用bitset存结点的真值表，用LCT维护一下树链，update的时候合并真值表即可。

要注意的是，LCT在reverse的时候左右子树，update的运算顺序会与实际不符。为了维护正确顺序，需要同时更新链上正向运算真值表和反向运算真值表，交换子树的时候把真值表交换。

↑否则WA一半数据（居然只有一半）

5 10 5
2 4
1 9
3 9
3 15
1 7
1 2
1 4
2 5
2 3
1 1 3 31
1 1 5 31
1 4 3 28
1 3 4 28
1 5 4 27
1 4 5 27
1 5 4 27
1 4 3 28
1 3 4 28

↑由于这个贪心顺序的问题，reverse的时候不能打个lazy标记就走，需要向下push一层。没注意到这个问题，多调了一个小时。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<bitset>
#include<vector>
#define LL unsigned long long
using namespace std;
const int mxn=100010;
LL read(){
    LL 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();}
    return x*f;
}
vector<int>ve[mxn];
struct node{
    int ch[2],fa;
    LL val;
    int tp;//位运算方式  
    bool rev;
}t[mxn];
struct table{
    bitset<64>f[2];//真值表 //哪些位置填0/1能得到1
}a[mxn],b[mxn],f[mxn];
inline bool isroot(int x){
    return t[t[x].fa].ch[0]!=x && t[t[x].fa].ch[1]!=x;
}
void init(bitset<64> &a,LL b,int tp){
    bitset<64> B=b;
    if(tp==1){a=a&B;}//&
    else if(tp==2){a=a|B;}//|
    else if(tp==3){a=a^B;}//^
    return;
}
table calc(const table &x,const table &y){
    bitset<64>B,C;
    B=(x.f[0]&y.f[1])|((~x.f[0])&y.f[0]);
    C=(x.f[1]&y.f[1])|((~x.f[1])&y.f[0]);
    return (table){B,C};
}
void update(int rt){
    a[rt]=f[rt];b[rt]=f[rt];
    int ls=t[rt].ch[0],rs=t[rt].ch[1];
    if(ls){
        a[rt]=calc(a[ls],a[rt]);b[rt]=calc(b[rt],b[ls]);
    }
    if(rs){
        a[rt]=calc(a[rt],a[rs]);b[rt]=calc(b[rs],b[rt]);
    }
    return;
}
void rever(int x){
    t[x].rev^=1;
    int &lc=t[x].ch[0],&rc=t[x].ch[1];
    swap(lc,rc);
    swap(a[x],b[x]);    
    return;
}
void PD(int x){
    if(t[x].rev){
        rever(t[x].ch[0]);
        rever(t[x].ch[1]);
        t[x].rev=0;
    }
    return;
}
void rotate(int x){
    int y=t[x].fa,z=t[y].fa,lc,rc;
    if(t[y].ch[0]==x)lc=0;else lc=1; rc=lc^1;
    if(!isroot(y))
        t[z].ch[t[z].ch[1]==y]=x;
    t[x].fa=z;t[y].fa=x;
    t[t[x].ch[rc]].fa=y;
    t[y].ch[lc]=t[x].ch[rc];
    t[x].ch[rc]=y;
    update(y);
    return;
}
int st[mxn],top=0;
void Splay(int x){
    st[top=1]=x;
    for(int i=x;!isroot(i);i=t[i].fa)st[++top]=t[i].fa;
    while(top)PD(st[top--]);
    while(!isroot(x)){
        int y=t[x].fa,z=t[y].fa;
        if(!isroot(y)){
            if((t[y].ch[0]==x)^(t[z].ch[0]==y))rotate(y);
            else rotate(x);
        }
        rotate(x);
    }
    update(x);
    return;
}
void access(int x){
    for(int y=0;x;x=t[x].fa){
        Splay(x);
        t[x].ch[1]=y;
        update(x);
        y=x;
    }
    return;
}
int dfn[mxn];
void mkroot(int x){
    access(x);Splay(x);
    rever(x);
    return;
}
void change(int x,int y,LL z){
    access(x);   Splay(x);
    t[x].tp=y;  t[x].val=z;
    f[x].f[1].set(); f[x].f[0].reset();
    init(f[x].f[0],t[x].val,t[x].tp);
    init(f[x].f[1],t[x].val,t[x].tp);
    update(x);
    return;
}
void query(int x,int y,LL z){
    mkroot(x);access(y);Splay(y);
    LL ans=0,now=0;
    for(int i=63;i>=0;i--){
        if(a[y].f[0][i]==1){
            ans+=1LL<<i;
        }
        else if(a[y].f[1][i]==1){
            if(now+(1LL<<i)<=z){
                now+=1LL<<i;
                ans+=1LL<<i;
            }
        }
    }
    printf("%llu
",ans);
    return;
}
int n,m,K;
void solve(){
    int Q,x,y;LL z;
    for(int i=1;i<=m;i++){
        Q=read();x=read();y=read();scanf("%llu",&z);
        if(Q==1)
            query(x,y,z);
        else
            change(x,y,z);
    }
    return;
}
void Build(int x,int fa){
    for(int i=0;i<ve[x].size();i++){
        if(ve[x][i]==fa)continue;
        t[ve[x][i]].fa=x;
        Build(ve[x][i],x);
    }
    return;
}
int main(){
    int i,j;
    n=read();m=read();K=read();
    for(i=1;i<=n;i++){
        t[i].tp=read();
        t[i].val=read();
        f[i].f[1].set();
        init(f[i].f[0],t[i].val,t[i].tp);
        init(f[i].f[1],t[i].val,t[i].tp);
    }
    int u,v;
    for(i=1;i<n;i++){
        u=read();v=read();
        ve[u].push_back(v); ve[v].push_back(u);
    }
    Build(1,0);
    solve();
    return 0;
}