BZOJ4817 [Sdoi2017] 树点涂色

题目链接

Solution

这题很???
我们把相同颜色的点之间连的边看成preferred edge
那么操作1就是access
查询的时候用链剖维护一下区间最值就行了。

Hints

然而LCT写挂了两次
先是rotate的时候把一个x打成了k,
然后是splay的时候没有判isroot(fa[x])。
一些注意的地方:
1、LCT和链剖的father要分开记。
2、access的时候要注意处理now断开的那部分子树。

Code

#include<bits/stdc++.h>
#define FIO "sample"
using namespace std;
typedef long long ll;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int maxn = 100010;

struct edge{
    int nxt,to;
    edge(){}
    edge(int nxt,int to):nxt(nxt),to(to){}
}e[maxn<<1];
template<typename T> inline void Max(T &x,T y) {if(x<y) x=y;}

int n,m,last[maxn],cnt=1,f[maxn],top[maxn],dfn[maxn],pos[maxn],dep[maxn],ch[maxn][2];
int sz[maxn],ind=0,mx[maxn<<2],tag[maxn<<2],son[maxn],fa[maxn];

inline void insert(int u,int v){e[++cnt]=edge(last[u],v);last[u]=cnt;}
inline void addedge(int u,int v){insert(u,v);insert(v,u);}

inline void dfs(int x)
{
    dep[x]=dep[f[x]]+1;
    sz[x]=1;son[x]=0;
    for(int i=last[x];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v^f[x])
        {
            f[v]=x;dfs(v);sz[x]+=sz[v];
            if(sz[v]>sz[son[x]]) son[x]=v;
        }
    }
}

inline void dfs2(int x,int chain)
{
    top[x]=chain;pos[dfn[x]=++ind]=x;
    if(son[x]) dfs2(son[x],chain);
    for(int i=last[x];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v^f[x]&&v^son[x])
            dfs2(v,v);
    }
}

inline int lca(int x,int y)
{
    while(top[x]^top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=f[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}

inline void update(int x)
{
    mx[x]=max(mx[x<<1],mx[x<<1|1]);
}

inline void pushdown(int x)
{
    if(tag[x])
    {
        int ls=x<<1,rs=x<<1|1;
        tag[ls]+=tag[x];
        tag[rs]+=tag[x];
        mx[ls]+=tag[x];
        mx[rs]+=tag[x];
        tag[x]=0;
    }
}

inline void build(int x,int l,int r)
{
    tag[x]=0;
    if(l==r){mx[x]=dep[pos[l]];return;}
    int mid=l+r>>1;
    build(x<<1,l,mid);build(x<<1|1,mid+1,r);
    update(x);
}

inline void modify(int x,int l,int r,int lx,int rx,int val)
{
    if(l>=lx&&r<=rx) {mx[x]+=val;tag[x]+=val;return;}
    int mid=l+r>>1;pushdown(x);
    if(lx<=mid) modify(x<<1,l,mid,lx,rx,val);
    if(rx>mid) modify(x<<1|1,mid+1,r,lx,rx,val);
    update(x);
}

inline int query(int x,int l,int r,int lx,int rx)
{
    if(l>=lx&&r<=rx) return mx[x];
    int mid=l+r>>1,res=0;pushdown(x);
    if(lx<=mid) Max(res,query(x<<1,l,mid,lx,rx));
    if(rx>mid) Max(res,query(x<<1|1,mid+1,r,lx,rx));
    return res;
}

inline bool isroot(int x) {return (ch[fa[x]][0]!=x && ch[fa[x]][1]!=x);}
#define ir isroot
inline int get(int x) {return ch[fa[x]][1]==x;}
#define gt get

inline void rotate(int x)
{
    int y=fa[x],z=fa[y],k=gt(x);
    if(!ir(y)) ch[z][gt(y)]=x;
    fa[ch[y][k]=ch[x][k^1]]=y;
    fa[fa[ch[x][k^1]=y]=x]=z;
}

inline void splay(int x)
{
    for(int y=fa[x];!ir(x);rotate(x),y=fa[x])
        if(!ir(y))
            rotate(gt(x)==gt(y)?y:x);
}

#define end(x) (dfn[x]+sz[x]-1)

inline void access(int x)
{
    for(int t=0;x;t=x,x=fa[x])
    {
        splay(x);
        if(ch[x][1])
        {
            int now=ch[x][1];
            while(ch[now][0]) now=ch[now][0];
            modify(1,1,n,dfn[now],end(now),1);
        }
        ch[x][1]=t;
        if(ch[x][1])
        {
            int now=ch[x][1];
            while(ch[now][0]) now=ch[now][0];
            modify(1,1,n,dfn[now],end(now),-1);
        }
    }
}

int main()
{
#ifdef dxymaster
    freopen(FIO".in","r",stdin);
    freopen(FIO".out","w",stdout);
#endif
    n=read(),m=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        addedge(u,v);
    }
    f[1]=0;dfs(1);dfs2(1,1);build(1,1,n);
    for(int i=1;i<=n;i++) fa[i]=f[i];
    while(m--)
    {
        int opt=read();
        if(opt==1) access(read());
        else if(opt==2)
        {
            int x=read(),y=read(),k=lca(x,y);int v=query(1,1,n,dfn[k],dfn[k]);
            printf("%d\n",query(1,1,n,dfn[x],dfn[x])+query(1,1,n,dfn[y],dfn[y])-(v<<1)+1);
        }
        else
        {
            int x=read();
            printf("%d\n",query(1,1,n,dfn[x],end(x)));
        }
    }

    return 0;
}

SCOI 2018 不知道干了什么记

省选复习

做了10联测,感觉被大佬们各种虐,有种省选完挂的预感啊。。。

上了OJ才发现自己rating好低。。。炫酷蓝紫色。。。

期间做了ZJOI Day1和一些不知道哪里来的题,看题发现自己啥都不会,只会暴力。。。

然而做完以后发现自己并不会暴力,只会瞎骗分。。。。

然而评测的时候发现,自己并不会骗分,只会报零。。。。

总之就是被各种吊打,只有最后一天的题稍微良心一点。。。写了傻逼的T1和T3.。。但是好像有很多人AK。。。。

省选集训 (Day -4 ~ Day -1)

Day -4

上午去神大ACM,只A了3到签到题。A迷之wa,交了十多发都被卡在了第11个点。。。。

佬队AK后提前离场了,吊打神大,%%%。

下午去中和中学。。好偏僻啊。。听说是在一个镇上???!!!

没去学校看,直接去酒店了。。。

Day -3

上午去听课了??不知道哪里的人来讲的。

讲的线性基,感觉好水啊。然后就开始突突突。

下午上机练习。中和的电脑配置看起来不错,但用着挺糟糕的。。

花了半个小时配环境(大半时间实在卸载。。)然后开始突突突。。

晚上会酒店,看了会儿题,然后突突突。。

Day -2

和前一天好像没啥区别。。

下午lxs发了一套题,把T1、T3写了。。

Day -1

同上

不过这次写的是T2和T3

Day 0

上午起来好困啊。。

以为是下午才模拟考,导致前一天晚上睡得晚。。。

T1傻逼DP。。写了2小时。。。我好菜啊。。(后来发现状态数多了一点,写复杂了。。但是懒得改了。。。)

T2会一个线段树上二分的log方做法。。。然而数据范围很水的样子。。好像这套题里所有的n都没有超过1e4的(雾)

于是写了n方暴力。事实证明我并不能够卡过。。。

T3好像是维护一个最小割。。并不知道怎么维护。。时间也不太够了,就写了一个网络流加一点小优化。。

结果T1T了3个点(真心慢),T2T了4个,T3T了2个。。。

然后下午去神大天街。

好好睡了一觉。

Day 1

早上起的很早,有点困。到了神大,发现两边都坐的是石室的。结果两人都进队了。被支配的恐惧有没有。。

T1写了4个小时。。乍眼一看以为是一道傻逼题。先是想用链剖维护,发现不会。然后又上动态点分。码了两百多行一测样例,然后想了想发现不对。然后觉得是道树套树裸题,发现写不来。

最后写了个跟树深度有关的方法,事实证明出题人没有恶意卡。

然后看T2,推了一下,发现是个二次剩余。但是模数1e16,觉得没法做。最后放弃了,写了个55分暴力。

然后看T3,发现不会。瞎写了一下。

然后,开始绝望。。

最后10分钟突然发现T2要乘爆long long,没时间了,果断选择不改了、继续绝望。

最后75+15+0

但是看大家分好像都很低的样子。。然而佬还是那么高,255碾压全场。。

Day2

密码好像是什么吃葡萄不吐葡萄皮。

T1发现是线段树维护一个凸函数。。看起来不是那么好写。。先放着。

T2计算几何??放弃。。。

T3是个什么玩意儿。我只会10分好不好。再看了一遍题,确认无误后,果断选择放弃。。

然后开始码T1。写了大概1h,调过了大样例。然后开始对拍。

可能是我的写法太丑了,对拍居然发现了4个错。。

然后调完,发现常数大。。可能要跑4、5秒。

各种卡常。

最后30+0+0.

Day 3

省赛完挂,退役AFO
要是明年再这样就真GG了