bzoj 3083: 遥远的国度

发布时间:2017-7-9 7:09:46编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"bzoj 3083: 遥远的国度 ",主要涉及到bzoj 3083: 遥远的国度 方面的内容,对于bzoj 3083: 遥远的国度 感兴趣的同学可以参考一下。

传送门

Description

  zcwwzdjn在追杀十分sb的zhx,而zhx逃入了一个遥远的国度。当zcwwzdjn准备进入遥远的国度继续追杀时,守护神RapiD阻拦了zcwwzdjn的去路,他需要zcwwzdjn完成任务后才能进入遥远的国度继续追杀。

  问题是这样的:遥远的国度有n个城市,这些城市之间由一些路连接且这些城市构成了一颗树。这个国度有一个首都,我们可以把这个首都看做整棵树的根,但遥远的国度比较奇怪,首都是随时有可能变为另外一个城市的。遥远的国度的每个城市有一个防御值,有些时候RapiD会使得某两个城市之间的路径上的所有城市的防御值都变为某个值。RapiD想知道在某个时候,如果把首都看做整棵树的根的话,那么以某个城市为根的子树的所有城市的防御值最小是多少。由于RapiD无法解决这个问题,所以他拦住了zcwwzdjn希望他能帮忙。但zcwwzdjn还要追杀sb的zhx,所以这个重大的问题就被转交到了你的手上。

链剖+倍增就可以了耶!

#include<cstdio>#include<algorithm>#define MN 210000#define lp p<<1#define rp (p<<1)|1#define int unsigned intusing namespace std;int read_p,read_ca,read_f;inline int read(){    read_p=0;read_ca=getchar();read_f=1;    while(read_ca<'0'||read_ca>'9') read_f=read_ca=='-'?-1:read_f,read_ca=getchar();    while(read_ca>='0'&&read_ca<='9') read_p=read_p*10+read_ca-48,read_ca=getchar();    return read_p*read_f;}struct na{int y,ne;}b[MN];int n,m,x,y,l[MN],num=0,opt,a[MN],fa[MN],de[MN],si[MN],son[MN],df[MN],lo[MN],to[MN],nm=0,root,c[MN<<2],s[MN<<2],f[MN][20];inline void in(int x,int y){b[++num].y=y;b[num].ne=l[x];l[x]=num;}inline void pd(int p){if (c[p]) c[lp]=s[lp]=c[rp]=s[rp]=c[p],c[p]=0;}void cg(int p,int l,int r,int L,int R,int k){    if (l==L&&r==R) c[p]=s[p]=k;else{        pd(p);        int mid=l+r>>1;        if (R<=mid) cg(lp,l,mid,L,R,k);else        if (L>mid) cg(rp,mid+1,r,L,R,k);else        cg(lp,l,mid,L,mid,k),cg(rp,mid+1,r,mid+1,R,k);        s[p]=min(s[lp],s[rp]);    }}int ask(int p,int l,int r,int L,int R){    if ((l==L&&r==R)||c[p]) return s[p];else{        int mid=l+r>>1;        if (R<=mid) return ask(lp,l,mid,L,R);else        if (L>mid) return ask(rp,mid+1,r,L,R);else        return min(ask(lp,l,mid,L,mid),ask(rp,mid+1,r,mid+1,R));    }}void dfs(int x){    si[x]=1;f[x][0]=fa[x];    for (int i=1;i<20;i++) f[x][i]=f[f[x][i-1]][i-1];    for (int i=l[x];i;i=b[i].ne)    if (b[i].y!=fa[x]){        de[b[i].y]=de[x]+1;fa[b[i].y]=x;dfs(b[i].y);        si[x]+=si[b[i].y];        if (si[b[i].y]>si[son[x]]) son[x]=b[i].y;    }}void DFS(int x,int f){    df[x]=++nm;cg(1,1,n,nm,nm,a[x]);to[x]=f;    if (son[x]) DFS(son[x],f);    for (int i=l[x];i;i=b[i].ne)    if (b[i].y!=son[x]&&b[i].y!=fa[x]) DFS(b[i].y,b[i].y);    lo[x]=nm;}inline void cg(){    int x,y,z;    x=read();y=read();z=read();    while(to[x]!=to[y]){        if (de[to[x]]<de[to[y]]) swap(x,y);        cg(1,1,n,df[to[x]],df[x],z);x=fa[to[x]];    }    if (de[x]<de[y]) swap(x,y);    cg(1,1,n,df[y],df[x],z);}inline void ask(){    int x=read(),y=root,mmh;    if (x==y) mmh=ask(1,1,n,1,n);else    if (df[x]<=df[y]&&df[y]<=lo[x]){        for (signed i=19;i>=0;i--)        if (f[y][i]&&de[f[y][i]]>de[x]) y=f[y][i];        mmh=ask(1,1,n,1,df[y]-1);if (lo[y]!=n) mmh=min(ask(1,1,n,lo[y]+1,n),mmh);    }else mmh=ask(1,1,n,df[x],lo[x]);    printf("%u\n",mmh);}signed main(){    n=read();m=read();    for (int i=1;i<n;i++) x=read(),y=read(),in(x,y),in(y,x);    for (int i=1;i<=n;i++) a[i]=read();    dfs(1);DFS(1,1);root=read();    while (m--){        opt=read();        if (opt==1) root=read();else if (opt==2) cg();else ask();    }}
View Code


上一篇:openvpn 初步使用
下一篇:doubleclick protobuf file load to project

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款