[SDOI2017]树点涂色-白红宇

[SDOI2017]树点涂色

阅读量：5223 次

发布时间：2019-06-14

本文共 4642 字，大约阅读时间需要 15 分钟。

题目描述

Bob有一棵

定义一条路径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。

Bob可能会进行这几种操作：

把点

2 x y

求

在以x为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值。

Bob一共会进行

输入输出格式

输入格式：

第一行两个数

接下来

输出格式：

每当出现2,3操作，输出一行。

如果是2操作，输出一个数表示路径的权值

如果是3操作，输出一个数表示权值的最大值

输入输出样例

输入样例#1：

5 61 22 33 43 52 4 53 31 42 4 51 52 4 5

输出样例#1：

说明

共10个测试点

测试点1， $1\leq n,m\leq10001≤n,m≤1000$

测试点2、3，没有2操作

测试点4、5，没有3操作

测试点6，树的生成方式是，对于 $i(2\leq i \leq n)i(2≤i≤n)，在1到i-1i−1中随机选一个点作为i的父节点。$

测试点7， $1\leq n,m\leq 500001≤n,m≤50000$

测试点8， $1\leq n \leq 500001≤n≤50000$

测试点9,10，无特殊限制

对所有数据， $1\leq n \leq 10^51≤n≤105，1\leq m \leq 10^51≤m≤105$

时间限制：1s

空间限制：128MB

维护一个LCT,每个Splay里都是颜色相同的点.那么操作2的答案就是这两个点路径上的虚边的数量+1. 操作3的答案就是子树中每个点到根的路径虚边最大值+1.因为每次操作1都会用一种新的颜色,那么2的答案=f[x]+f[y]-2*f[lca(x,y)]+1.f[x]代表x到根的路径上的虚边数量.

然后这个东西显然树链剖分用线段树来维护,顺便求出lca.那么操作2为单点查询,操作3为区间查询(dfn).

然后再考虑操作1对查询的影响.

用LCT中的access操作,每次将一条实边变成虚边的时候,将这颗子树中的值全部加1,虚边变实边相反. 这里有一个细节没有考虑到,因为这条路径是用Splay存的,那么原树上与这条要修改的边相连的点并不是Splay中与这条边相连的那个点. 所以区间修改时要找最浅的那个点,即为Splay中那颗子树的最左边的点.

1 #include
     
        2 #define ls o*2  3 #define rs o*2+1  4 #define pre t[x].fa  5 #define LS t[x].ch[0]  6 #define RS t[x].ch[1]  7 #define maxn 100010  8 #define RG register  9 using namespace std; 10 struct Edge{ 11   int nex,to; 12 }e[maxn*2]; 13 struct lct{
   int w,ch[2],fa;}t[maxn]; 14 int head[maxn],edge=0,top[maxn],dfn[maxn],dfp[maxn],dad[maxn],ed[maxn],deep[maxn],son[maxn],size[maxn]; 15 int n,b[maxn*4],lazy[maxn*4]; 16 inline void add(int from,int to){ 17   e[++edge].nex=head[from]; 18   e[edge].to=to; 19   head[from]=edge; 20 } 21 void dfs1(int x,int fa){ 22   size[x]=1; 23   for(RG int i=head[x];i;i=e[i].nex){ 24     int v=e[i].to; 25     if(v==fa) continue; 26     deep[v]=deep[x]+1; 27     dad[v]=x;t[v].fa=x; 28     dfs1(v,x); 29     size[x]+=size[v]; 30     if(size[v]>size[son[x]])son[x]=v; 31   } 32 } 33 int de=0; 34 void dfs2(int x,int fa){ 35   dfn[x]=++de;dfp[de]=x; 36   if(son[x])top[son[x]]=top[x],dfs2(son[x],x); 37   for(int i=head[x];i;i=e[i].nex){ 38     int v=e[i].to; 39     if(v==fa || v==son[x])continue; 40     top[v]=v; 41     dfs2(v,x); 42   } 43   ed[x]=de; 44 } 45 void build(int o,int l,int r){ 46   if(l==r){b[o]=deep[dfp[l]];return;} 47   int mid=(l+r)>>1; 48   build(ls,l,mid);build(rs,mid+1,r); 49   b[o]=max(b[ls],b[rs]); 50 } 51 inline void down(int o){ 52   if(lazy[o]){ 53     int k=lazy[o];lazy[o]=0; 54     b[ls]+=k,b[rs]+=k,lazy[ls]+=k,lazy[rs]+=k; 55   } 56 } 57 void change(int o,int l,int r,int u,int v,int w){ 58   if(l!=r) down(o); 59   if(l>v || r
      
       =u && r<=v){b[o]+=w,lazy[o]+=w;return;} 61   int mid=(l+r)>>1; 62   if(v<=mid) change(ls,l,mid,u,v,w); 63   else if(u>mid) change(rs,mid+1,r,u,v,w); 64   else change(ls,l,mid,u,mid,w),change(rs,mid+1,r,mid+1,v,w); 65   b[o]=max(b[ls],b[rs]); 66 } 67 inline bool isrt(int x){
   return t[pre].ch[0]!=x && t[pre].ch[1]!=x;} 68 inline bool Son(int x){
   return t[pre].ch[1]==x;} 69 inline void Rotate(int x){ 70   int f=t[x].fa,g=t[f].fa,c=Son(x); 71   if(!isrt(f)) t[g].ch[Son(f)]=x; 72   t[x].fa=g; 73   t[f].ch[c]=t[x].ch[c^1],t[t[f].ch[c]].fa=f; 74   t[x].ch[c^1]=f,t[f].fa=x; 75 } 76 inline void Splay(int x){ 77   for(;!isrt(x);Rotate(x)) 78     if(!isrt(pre)) Rotate(Son(pre)==Son(x)?pre:x); 79 } 80 inline void access(int x){ 81   for(RG int y=0;x;y=x,x=pre){ 82     Splay(x);if(RS){ 83       int kp=RS; 84       while(t[kp].ch[0])kp=t[kp].ch[0]; 85       change(1,1,n,dfn[kp],ed[kp],1); 86     } 87     RS=y;if(RS){ 88       int kp=RS; 89       while(t[kp].ch[0])kp=t[kp].ch[0]; 90       change(1,1,n,dfn[kp],ed[kp],-1); 91     } 92   } 93 } 94 int Find(int o,int l,int r,int p){ 95   if(l!=r) down(o); 96   if(l==r) return b[o]; 97   int mid=(l+r)>>1; 98   if(p<=mid)return Find(ls,l,mid,p); 99   else return Find(rs,mid+1,r,p);100 }101 int query(int o,int l,int r,int u,int v){102   if(l!=r) down(o);103   if(l>v || r
       
        =u && r<=v) return b[o];105   int mid=(l+r)>>1;106   if(v<=mid) return query(ls,l,mid,u,v);107   else if(u>mid) return query(rs,mid+1,r,u,v);108   else return max(query(ls,l,mid,u,mid),query(rs,mid+1,r,mid+1,v));109 }110 inline void lca(int x,int y){111   int xx=x,yy=y,LCA;112   while(top[x]!=top[y]){113     if(deep[top[x]]>deep[top[y]])x=dad[top[x]];114     else y=dad[top[y]];115   }116   LCA=deep[x]>deep[y]?y:x;117   printf("%d\n",Find(1,1,n,dfn[xx])+Find(1,1,n,dfn[yy])-2*Find(1,1,n,dfn[LCA])+1);118 }119 int main(){120   int m,type,x,y;121   scanf("%d%d",&n,&m);122   for(RG int i=1;i