首页 > 代码库 > Bzoj4817 [Sdoi2017]树点涂色
Bzoj4817 [Sdoi2017]树点涂色
Submit: 301 Solved: 182
Description
Bob有一棵n个点的有根树，其中1号点是根节点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。定义一条路
径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。Bob可能会进行这几种操作：
1 x:
把点x到根节点的路径上所有的点染上一种没有用过的新颜色。
2 x y:
求x到y的路径的权值。
3 x y:
在以x为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值。
Bob一共会进行m次操作
Input
第一行两个数n,m。
接下来n-1行，每行两个数a,b，表示a与b之间有一条边。
接下来m行，表示操作，格式见题目描述
1<=n,m<=100000
Output
每当出现2,3操作，输出一行。
如果是2操作，输出一个数表示路径的权值
如果是3操作，输出一个数表示权值的最大值
Sample Input
5 6
1 2
2 3
3 4
3 5
2 4 5
3 3
1 4
2 4 5
1 5
2 4 5
1 2
2 3
3 4
3 5
2 4 5
3 3
1 4
2 4 5
1 5
2 4 5
Sample Output
3
4
2
2
4
2
2
HINT
Source
鸣谢infinityedge上传
Bzoj3779 重组病毒 ←这个的弱化版
树 线段树 LCT LCA
基本上和上面那道题一样
查询链上颜色树的时候做差分即可，$ ans=val(x)+val(y)-2*val(LCA(x,y))+1 $
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #define LL long long 9 using namespace std; 10 const int mxn=100010; 11 int read(){ 12 int x=0,f=1;char ch=getchar(); 13 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 14 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 15 return x*f; 16 } 17 struct edge{ 18 int v,nxt; 19 }e[mxn<<1]; 20 int hd[mxn],mct=0; 21 void add_edge(int u,int v){ 22 e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct;return; 23 } 24 namespace TC{ 25 struct node{ 26 int fa,top,son; 27 int sz; 28 }t[mxn]; 29 int dep[mxn],ind[mxn],out[mxn],dtime; 30 int mp[mxn]; 31 void DFS(int u,int ff){ 32 dep[u]=dep[ff]+1; 33 t[u].sz++; 34 for(int i=hd[u],v;i;i=e[i].nxt){ 35 if(e[i].v==ff)continue; 36 v=e[i].v; 37 t[v].fa=u; 38 DFS(v,u); 39 t[u].sz+=t[v].sz; 40 if(t[v].sz>t[t[u].son].sz)t[u].son=v; 41 } 42 return; 43 } 44 void DFS2(int u,int top){ 45 ind[u]=++dtime; 46 mp[dtime]=u; 47 t[u].top=top; 48 if(t[u].son){ 49 DFS2(t[u].son,top); 50 for(int i=hd[u];i;i=e[i].nxt){ 51 if(e[i].v==t[u].son || e[i].v==t[u].fa)continue; 52 DFS2(e[i].v,e[i].v); 53 } 54 } 55 out[u]=dtime; 56 return; 57 } 58 int LCA(int x,int y){ 59 while(t[x].top!=t[y].top){ 60 if(dep[t[x].top]<dep[t[y].top])swap(x,y); 61 x=t[t[x].top].fa; 62 } 63 if(dep[x]<dep[y])return x; 64 else return y; 65 } 66 } 67 int n,m,nowroot; 68 struct SGT{ 69 #define lc rt<<1 70 #define rc rt<<1|1 71 struct node{ 72 LL smm,mk,mx; 73 }t[mxn<<2]; 74 void pushup(int rt){ 75 t[rt].smm=t[lc].smm+t[rc].smm; 76 t[rt].mx=max(t[lc].mx,t[rc].mx); 77 return; 78 } 79 inline void PD(int l,int r,int rt){ 80 if(t[rt].mk){ 81 t[lc].mk+=t[rt].mk; 82 t[rc].mk+=t[rt].mk; 83 int mid=(l+r)>>1; 84 t[lc].smm+=t[rt].mk*(LL)(mid-l+1); 85 t[rc].smm+=t[rt].mk*(LL)(r-mid); 86 t[lc].mx+=t[rt].mk;t[rc].mx+=t[rt].mk; 87 t[rt].mk=0; 88 } 89 return; 90 } 91 void Build(int l,int r,int rt){ 92 if(l==r){ 93 t[rt].smm=t[rt].mx=TC::dep[TC::mp[l]]; return; 94 } 95 int mid=(l+r)>>1; 96 Build(l,mid,lc);Build(mid+1,r,rc); 97 pushup(rt); 98 return; 99 }100 void update(int L,int R,int v,int l,int r,int rt){101 if(L>R)return;102 if(L<=l && r<=R){103 t[rt].mk+=v;104 t[rt].smm+=(LL)v*(r-l+1);105 t[rt].mx+=v;106 return;107 }108 PD(l,r,rt);109 int mid=(l+r)>>1;110 if(L<=mid)update(L,R,v,l,mid,lc);111 if(R>mid)update(L,R,v,mid+1,r,rc);112 pushup(rt);113 return;114 }115 LL qmax(int L,int R,int l,int r,int rt){116 if(L>R)return -1e9;117 if(L<=l && r<=R){return t[rt].mx;}118 PD(l,r,rt);119 int mid=(l+r)>>1;120 LL res=-1e9;121 if(L<=mid)res=max(res,qmax(L,R,l,mid,lc));122 if(R>mid)res=max(res,qmax(L,R,mid+1,r,rc));123 return res;124 }125 LL qsum(int p,int l,int r,int rt){126 if(l==r){return t[rt].smm;}127 PD(l,r,rt);128 LL res=0;129 int mid=(l+r)>>1;130 if(p<=mid)res=qsum(p,l,mid,lc);131 else res=qsum(p,mid+1,r,rc);132 pushup(rt);133 return res;134 }135 void Q_UPD(int x,int v){136 using namespace TC; 137 update(ind[x],out[x],v,1,n,1);138 return;139 }140 LL Query(int x){141 using namespace TC;142 // printf("___:%d\n",x);143 int y=read();144 int tmp=TC::LCA(x,y);145 LL ans=qsum(ind[x],1,n,1)+qsum(ind[y],1,n,1)-2*qsum(ind[tmp],1,n,1)+1;146 printf("%lld\n",ans);147 return ans;148 }149 LL Q_max(int x){150 using namespace TC;151 LL ans=0;152 ans=qmax(ind[x],out[x],1,n,1);153 printf("%lld\n",ans);154 return ans;155 }156 #undef lc157 #undef rc158 }sgt;159 struct LCT{160 int ch[mxn][2],fa[mxn];161 bool rev[mxn];162 int st[mxn],top;163 inline bool isroot(int x){return (ch[fa[x]][0]!=x && ch[fa[x]][1]!=x);}164 void PD(int rt){165 if(rev[rt]){166 rev[ch[rt][0]]^=1; rev[ch[rt][1]]^=1;167 swap(ch[rt][0],ch[rt][1]);168 rev[rt]^=1;169 }170 return;171 }172 void rotate(int x){173 int y=fa[x],z=fa[y],lc,rc;174 if(ch[y][0]==x)lc=0;else lc=1; rc=lc^1;175 if(!isroot(y)) ch[z][ch[z][1]==y]=x;176 fa[x]=z;fa[y]=x;177 fa[ch[x][rc]]=y;178 ch[y][lc]=ch[x][rc]; ch[x][rc]=y;179 return;180 }181 void Splay(int x){182 st[top=1]=x;183 for(int i=x;!isroot(i);i=fa[i]) st[++top]=fa[i];184 while(top)PD(st[top--]);185 while(!isroot(x)){186 int y=fa[x],z=fa[y];187 if(!isroot(y)){188 if((ch[z][0]==y)^(ch[y][0]==x))rotate(x);189 else rotate(y);190 }191 rotate(x);192 }193 }194 void access(int x){195 for(int y=0;x;x=fa[x]){196 Splay(x);197 if(ch[x][1]){198 int now=ch[x][1];199 PD(now);200 while(ch[now][0]){now=ch[now][0];PD(now);}201 sgt.Q_UPD(now,1);202 }203 if(y){204 int now=y;205 PD(now);206 while(ch[now][0]){now=ch[now][0];PD(now);}207 sgt.Q_UPD(now,-1);208 }209 ch[x][1]=y;210 y=x;211 }212 return;213 }214 /* void mkroot(int x){215 access(x);Splay(x);216 rev[x]^=1;217 nowroot=x;218 return;219 }*/220 }LT;221 void solve(){222 int x,opt;223 while(m--){224 scanf("%d%d",&opt,&x);225 if(opt==1){LT.access(x);continue;}226 if(opt==2){sgt.Query(x);continue;}227 if(opt==3){sgt.Q_max(x);continue;}228 // else Debug();229 }230 return;231 }232 int main(){233 // freopen("paint1.in","r",stdin);234 // freopen("out2.txt","w",stdout);235 int i,j;236 n=read();m=read();237 int u,v;238 for(i=1;i<n;i++){239 u=read();v=read();240 add_edge(u,v);add_edge(v,u);241 }242 TC::DFS(1,0);243 TC::DFS2(1,1);244 for(i=1;i<=n;i++) LT.fa[i]=TC::t[i].fa; 245 sgt.Build(1,n,1);246 solve();247 return 0;248 }
Bzoj4817 [Sdoi2017]树点涂色
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。