首页 > 代码库 > BZOJ3083: 遥远的国度
BZOJ3083: 遥远的国度
3083: 遥远的国度
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1045 Solved: 249
[Submit][Status]
Description
描述
zcwwzdjn在追杀十分sb的zhx，而zhx逃入了一个遥远的国度。当zcwwzdjn准备进入遥远的国度继续追杀时，守护神RapiD阻拦了zcwwzdjn的去路，他需要zcwwzdjn完成任务后才能进入遥远的国度继续追杀。
问题是这样的：遥远的国度有n个城市，这些城市之间由一些路连接且这些城市构成了一颗树。这个国度有一个首都，我们可以把这个首都看做整棵树的根，但遥远的国度比较奇怪，首都是随时有可能变为另外一个城市的。遥远的国度的每个城市有一个防御值，有些时候RapiD会使得某两个城市之间的路径上的所有城市的防御值都变为某个值。RapiD想知道在某个时候，如果把首都看做整棵树的根的话，那么以某个城市为根的子树的所有城市的防御值最小是多少。由于RapiD无法解决这个问题，所以他拦住了zcwwzdjn希望他能帮忙。但zcwwzdjn还要追杀sb的zhx，所以这个重大的问题就被转交到了你的手上。
Input
第1行两个整数n m，代表城市个数和操作数。
第2行至第n行，每行两个整数 u v，代表城市u和城市v之间有一条路。
第n+1行，有n个整数，代表所有点的初始防御值。
第n+2行一个整数 id，代表初始的首都为id。
第n+3行至第n+m+2行，首先有一个整数opt，如果opt=1，接下来有一个整数id，代表把首都修改为id；如果opt=2，接下来有三个整数p1 p2 v，代表将p1 p2路径上的所有城市的防御值修改为v；如果opt=3，接下来有一个整数 id，代表询问以城市id为根的子树中的最小防御值。
Output
对于每个opt=3的操作，输出一行代表对应子树的最小点权值。
Sample Input
3 7
1 2
1 3
1 2 3
1
3 1
2 1 1 6
3 1
2 2 2 5
3 1
2 3 3 4
3 1
1 2
1 3
1 2 3
1
3 1
2 1 1 6
3 1
2 2 2 5
3 1
2 3 3 4
3 1
Sample Output
1
2
3
4
提示
对于20%的数据，n<=1000 m<=1000。
对于另外10%的数据，n<=100000，m<=100000，保证修改为单点修改。
对于另外10%的数据，n<=100000，m<=100000，保证树为一条链。
对于另外10%的数据，n<=100000，m<=100000，没有修改首都的操作。
对于100%的数据，n<=100000，m<=100000，0<所有权值<=2^31。
2
3
4
提示
对于20%的数据，n<=1000 m<=1000。
对于另外10%的数据，n<=100000，m<=100000，保证修改为单点修改。
对于另外10%的数据，n<=100000，m<=100000，保证树为一条链。
对于另外10%的数据，n<=100000，m<=100000，没有修改首都的操作。
对于100%的数据，n<=100000，m<=100000，0<所有权值<=2^31。
HINT
Source
zhonghaoxi提供
题解：
好激动，居然在上自习之前过了这道题。。。
因为是树上路径修改所以树链剖分来搞
因为要查询子树最小所以要用dfs序
如果一起的话我们可以把两者结合起来！
但是怎么结合起来？
实际上我们树链剖分的时候给每个点新编的号就可以作为l[x]！！！
然后就和 树 那题一样了。
代码：
View Code
好激动，居然在上自习之前过了这道题。。。
因为是树上路径修改所以树链剖分来搞
因为要查询子树最小所以要用dfs序
如果一起的话我们可以把两者结合起来！
但是怎么结合起来？
实际上我们树链剖分的时候给每个点新编的号就可以作为l[x]！！！
然后就和 树 那题一样了。
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 200000+5 26 27 #define maxm 500+100 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 int n,m,q,rt,tot,dep[maxn],head[maxn],s[maxn],f[maxn][20],w[maxn],id[maxn]; 61 int l[maxn],r[maxn],top[maxn],son[maxn]; 62 struct edge{int go,next;}e[2*maxn]; 63 struct seg{int l,r,mi,tag;}t[4*maxn]; 64 inline void insert(int x,int y) 65 { 66 e[++tot]=(edge){y,head[x]};head[x]=tot; 67 e[++tot]=(edge){x,head[y]};head[y]=tot; 68 } 69 inline void dfs(int x) 70 { 71 for1(i,18)if((1<<i)<=dep[x])f[x][i]=f[f[x][i-1]][i-1];else break; 72 s[x]=1; 73 for(int i=head[x],y=son[x]=0;i;i=e[i].next) 74 if(!s[y=e[i].go]) 75 { 76 dep[y]=dep[x]+1;f[y][0]=x; 77 dfs(y); 78 s[x]+=s[y]; 79 if(s[y]>s[son[x]])son[x]=y; 80 } 81 } 82 inline void dfs2(int x,int chain) 83 { 84 l[x]=++m;id[m]=x;top[x]=chain; 85 if(son[x])dfs2(son[x],chain); 86 for(int i=head[x],y;i;i=e[i].next) 87 if(!l[y=e[i].go]&&y!=son[x])dfs2(y,y); 88 r[x]=m; 89 } 90 inline void pushup(int k) 91 { 92 t[k].mi=min(t[k<<1].mi,t[k<<1|1].mi); 93 } 94 inline void update(int k,int z) 95 { 96 t[k].mi=t[k].tag=z; 97 } 98 inline void pushdown(int k) 99 {100 if(t[k].tag==-1)return;101 update(k<<1,t[k].tag);102 update(k<<1|1,t[k].tag);103 t[k].tag=-1;104 }105 inline void build(int k,int l,int r)106 {107 t[k].l=l;t[k].r=r;int mid=(l+r)>>1;t[k].tag=-1;108 if(l==r){t[k].mi=w[id[l]];return;}109 build(k<<1,l,mid);build(k<<1|1,mid+1,r);110 pushup(k);111 }112 inline void change(int k,int x,int y,int z)113 {114 int l=t[k].l,r=t[k].r,mid=(l+r)>>1;115 if(l==x&&r==y){update(k,z);return;}116 pushdown(k);117 if(y<=mid)change(k<<1,x,y,z);118 else if(x>mid)change(k<<1|1,x,y,z);119 else change(k<<1,x,mid,z),change(k<<1|1,mid+1,y,z);120 pushup(k);121 }122 inline int query(int k,int x,int y)123 {124 int l=t[k].l,r=t[k].r,mid=(l+r)>>1;125 if(l==x&&r==y)return t[k].mi;126 pushdown(k);127 if(y<=mid)return query(k<<1,x,y);128 else if(x>mid)return query(k<<1|1,x,y);129 else return min(query(k<<1,x,mid),query(k<<1|1,mid+1,y));130 }131 132 int main()133 134 {135 136 freopen("input.txt","r",stdin);137 138 freopen("output.txt","w",stdout);139 140 n=read();q=read();141 for1(i,n-1)insert(read(),read());142 dfs(1);143 dfs2(1,1);144 for1(i,n)w[i]=read();145 build(1,1,m);146 rt=read();147 while(q--)148 {149 int ch=read();150 if(ch==1)rt=read();151 else if(ch==2)152 {153 int x=read(),y=read(),z=read();154 while(top[x]!=top[y])155 {156 if(dep[top[x]]<dep[top[y]])swap(x,y);157 change(1,l[top[x]],l[x],z);158 x=f[top[x]][0];159 }160 if(dep[x]>dep[y])swap(x,y);161 change(1,l[x],l[y],z);162 }163 else 164 {165 int x=read();166 if(x==rt)printf("%d\n",t[1].mi);167 else if(l[x]<=l[rt]&&r[x]>=r[rt])168 {169 int t=dep[rt]-dep[x]-1,y=rt,ans=inf;170 for3(i,18,0)if(t&(1<<i))y=f[y][i];171 if(1<=l[y]-1)ans=min(ans,query(1,1,l[y]-1));172 if(r[y]+1<=n)ans=min(ans,query(1,r[y]+1,n));173 printf("%d\n",ans);174 }else printf("%d\n",query(1,l[x],r[x]));175 }176 } 177 178 return 0;179 180 }
这才发现原来树链剖分的本质就是dfs序，只不过在把一些点映射到一个区间为了让每次查询的次数少，我们尽量使主链上分的点多一点。
归根结底，都是把树上问题转化到序列上来搞，然后就可以线段树来维护了。orz！
BZOJ3083: 遥远的国度
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。