树链剖分/dfs序

　　其实过了以后就好搞了……

　　链修改+子树查询+换根

　　其实静态树的换根直接树链剖分就可以搞了……

　　因为其实只有一样变了：子树

　　如果root在x的子树中（以1为根dfs的时候），那么现在x的子树就变成了整个dfs序中，除去含有root的那个子树的剩下的部分，画个图大概就是这样：（红色部分为现在的子树）

　　我们发现，这种子树由于换根而产生变化的情况，仅当在以1为根时的树中，x是new_root的祖先时发生，那么我们判断这种情况是否发生只需这样：if (start[x]<=start[root] && end[x]>=end[root]) ......

　　而其他情况？则和原来一样啦~子树并没有变化，对吧~

　　那么我们就可以搞了……

WA了几发：这题中点权的范围是0~2147483647（P.S.我一开始还以为得开unsigned int，因为写的是$\leq2^{31}$……）所以不能认为tag=0就是没有标记，而应该用-1作为空标记……

1 /**************************************************************  2     Problem: 3083  3     User: Tunix  4     Language: C++  5     Result: Accepted  6     Time:4444 ms  7     Memory:23172 kb  8 ****************************************************************/  9   10 //BZOJ 3083 11 #include
      
        12 #include
       
         13 #include
        
          14 #include
         
           15 #include
          
            16 #define rep(i,n) for(int i=0;i
           
            =n;--i) 19 #define pb push_back 20 using namespace std; 21 typedef long long LL; 22 inline int getint(){ 23 int r=1,v=0; char ch=getchar(); 24 for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-1; 25 for(; isdigit(ch);ch=getchar()) v=v*10-'0'+ch; 26 return r*v; 27 } 28 const int N=100010; 29 const int INF=2147483647; 30 /*******************template********************/ 31 int to[N<<1],next[N<<1],head[N],cnt; 32 void add(int x,int y){ 33 to[++cnt]=y; next[cnt]=head[x]; head[x]=cnt; 34 to[++cnt]=x; next[cnt]=head[y]; head[y]=cnt; 35 } 36 int t[N<<2],mn[N<<2]; 37 //t[o]表示set标记 38 #define mid (l+r>>1) 39 #define L (o<<1) 40 #define R (o<<1|1) 41 void Push_down(int o,int l,int r){ 42 if (t[o]!=-1){ 43 mn[L]=mn[R]=t[L]=t[R]=t[o]; 44 t[o]=-1; 45 } 46 } 47 void maintain(int o,int l,int r){ 48 mn[o]=min(mn[L],mn[R]); 49 } 50 void update(int o,int l,int r,int ql,int qr,int v){ 51 if (ql<=l && qr>=r) t[o]=mn[o]=v; 52 else{ 53 Push_down(o,l,r); 54 if (ql<=mid) update(L,l,mid,ql,qr,v); 55 if (qr>mid) update(R,mid+1,r,ql,qr,v); 56 maintain(o,l,r); 57 } 58 } 59 int query(int o,int l,int r,int ql,int qr){ 60 if (ql>qr) return INF; 61 if (ql<=l && qr>=r) return mn[o]; 62 else{ 63 int ans=INF; 64 Push_down(o,l,r); 65 if (ql<=mid) ans=min(ans,query(L,l,mid,ql,qr)); 66 if (qr>mid) ans=min(ans,query(R,mid+1,r,ql,qr)); 67 return ans; 68 } 69 } 70 int n,m,rt; 71 int a[N]; 72 int fa[N][20],st[N],ed[N],son[N],dep[N],size[N],top[N],tot; 73 void dfs(int x){ 74 size[x]=1; son[x]=0; 75 F(i,1,17) 76 if (dep[x]>=(1<
            
             mx) son[x]=to[i],mx=size[to[i]]; 86 } 87 } 88 bool vis[N]; 89 void connect(int x,int f){ 90 vis[x]=1; top[x]=f; 91 st[x]=++tot; 92 if (son[x]) connect(son[x],f); 93 94 for(int i=head[x];i;i=next[i]) 95 if (!vis[to[i]]) 96 connect(to[i],to[i]); 97 ed[x]=tot; 98 } 99 void modify(int x,int y,int v){100 while(top[x]!=top[y]){101 if (dep[top[x]]
             
              dep[y]) swap(x,y);106 update(1,1,n,st[x],st[y],v);107 }108 109 int main(){110 #ifndef ONLINE_JUDGE111 freopen("3083.in","r",stdin);112 // freopen("3083.out","w",stdout);113 #endif114 n=getint(); m=getint();115 F(i,2,n){116 int x=getint(),y=getint();117 add(x,y);118 }119 dfs(1);120 connect(1,1);121 memset(t,-1,sizeof t);122 F(i,1,n){123 a[i]=getint();124 update(1,1,n,st[i],st[i],a[i]);125 }126 rt=getint();127 F(i,1,m){128 int cmd=getint();129 if (cmd==1){130 rt=getint();131 }else if (cmd==2){132 int x=getint(),y=getint();133 int v=getint();134 modify(x,y,v);135 }else if (cmd==3){136 int x=getint();137 if (st[rt]>=st[x] && ed[rt]<=ed[x]){138 int y=rt,t=dep[rt]-dep[x]-1,ans=INF;139 D(i,17,0) if (t&(1<
              
               =ed[y]+1) ans=min(ans,query(1,1,n,ed[y]+1,n));142 printf("%d\n",ans);143 }else{144 printf("%d\n",query(1,1,n,st[x],ed[x]));145 }146 }147 }148 return 0;149 }

View Code

3083: 遥远的国度

Time Limit: 10 Sec Memory Limit: 1280 MB

Submit: 1370 Solved: 335

[][][]

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

3 1

2 1 1 6

3 1

2 2 2 5

3 1

2 3 3 4

3 1

Sample Output

提示

对于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

[ ][ ][ ]

转载于:https://www.cnblogs.com/Tunix/p/4501608.html

你可能感兴趣的文章