遥远的行星？ 神奇的国度？
NO，遥远的国度.
这题真皮OVO
考虑换根之后只有两种情况答案会变
一是根与询问点重合 答案整棵树
二是在询问点的子树内，这时候需要……枚举子树树根！
然后用dfs序来判断，这玩意是连续的（嗯……？），而且在每个子树内也是连续的（！）
锁定在哪颗子树内！
|
1 |
if (dfn[child]<=dfn[croot] && dfn[child]+tsize[child]-1>=dfn[croot]) |
然后你抓着这个子树的根节点把它拎起来，这整棵树其余的部分就耷拉到下面了
然后你就会发现这时候实际是询问这个红色的部分
然后就行了。
画风奇怪？？
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<iterator> #include<cstdlib> #include<queue> #include<vector> using namespace std; struct segment_tree { int l,r,w,tag; bool has_tag; } SGT[400010]={0}; struct ed { int pre,to; } edge[200010]={0}; int nodenum,at=1,pointer[100010]={0},fx,tx,nodev[100010]={0},croot; int anc[100010],topx[100010],tsize[100010],hson[100010],dfn[100010],depth[100010]; int tstamp=0,nnv[100010]={0}; int l[100010][22]={0}; int opt,lx,rx,val,typ,ux,vx; inline void readx(int& x) { x=0; int k=1; register char ch=0; while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; } while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); } x*=k; } inline void Insert() { at++; edge[at].pre=pointer[fx]; edge[at].to=tx; pointer[fx]=at; at++; edge[at].pre=pointer[tx]; edge[at].to=fx; pointer[tx]=at; } inline void Fancy(int nownode,int nowdep,int fa) { //LCA l[nownode][0]=fa; for (int i=1;i<=20;i++) l[nownode][i]=l[l[nownode][i-1]][i-1]; //find heavy son depth[nownode]=nowdep; anc[nownode]=fa; tsize[nownode]=1; for (int prex=pointer[nownode];prex;prex=edge[prex].pre) if (edge[prex].to!=fa) { Fancy(edge[prex].to,nowdep+1,nownode); tsize[nownode]+=tsize[edge[prex].to]; if (tsize[edge[prex].to]>tsize[hson[nownode]]) hson[nownode]=edge[prex].to; } } inline void Dreams(int nownode,int src) { topx[nownode]=src; dfn[nownode]=++tstamp; nnv[tstamp]=nodev[nownode]; if (hson[nownode]) Dreams(hson[nownode],src); for (int prex=pointer[nownode];prex;prex=edge[prex].pre) if (edge[prex].to!=hson[nownode] && edge[prex].to!=anc[nownode]) Dreams(edge[prex].to,edge[prex].to); } inline void BuildTree(int lxx,int rxx,int inx) { SGT[inx].l=lxx; SGT[inx].r=rxx; if (lxx==rxx) { SGT[inx].w=nnv[lxx]; return; } int mid=(lxx+rxx)>>1; BuildTree(lxx,mid,inx<<1); BuildTree(mid+1,rxx,inx<<1|1); SGT[inx].w=min(SGT[inx<<1].w,SGT[inx<<1|1].w); } inline void pushdown(int inx) { SGT[inx<<1].tag=SGT[inx<<1|1].tag=SGT[inx].tag; SGT[inx<<1].has_tag=SGT[inx<<1|1].has_tag=true; SGT[inx<<1].w=SGT[inx<<1|1].w=SGT[inx].tag; SGT[inx].tag=0; SGT[inx].has_tag=false; } inline void update(int inx) { if (SGT[inx].l>=lx && SGT[inx].r<=rx) { SGT[inx].w=val; SGT[inx].tag=val; SGT[inx].has_tag=true; return; } if (SGT[inx].has_tag) pushdown(inx); int mid=(SGT[inx].l+SGT[inx].r)>>1; if (lx<=mid) update(inx<<1); if (rx>mid) update(inx<<1|1); SGT[inx].w=min(SGT[inx<<1].w,SGT[inx<<1|1].w); } inline int query(int inx) { if (SGT[inx].l>=lx && SGT[inx].r<=rx) return SGT[inx].w; if (SGT[inx].has_tag) pushdown(inx); int mid=(SGT[inx].l+SGT[inx].r)>>1,ret=2*1e9; if (lx<=mid) ret=query(inx<<1); if (rx>mid) ret=min(ret,query(inx<<1|1)); SGT[inx].w=min(SGT[inx<<1].w,SGT[inx<<1|1].w); return ret; } inline int LCA(int u,int v) { if (depth[u]<depth[v]) swap(u,v); for (int i=20;i>=0;i--) if (depth[l[u][i]]>=depth[v]) u=l[u][i]; if (u==v) return u; for (int i=20;i>=0;i--) if (l[u][i]!=l[v][i]) { u=l[u][i]; v=l[v][i]; } return anc[u]; } inline void upd_range(int u,int v) { while (topx[u]!=topx[v]) { if (depth[topx[u]]<depth[topx[v]]) swap(u,v); lx=dfn[topx[u]]; rx=dfn[u]; update(1); u=anc[topx[u]]; } if (depth[u]<depth[v]) swap(u,v); lx=dfn[v]; rx=dfn[u]; update(1); } inline int solve(int u) { if (u==croot) { lx=1; rx=tstamp; return query(1); } else if (LCA(croot,u)!=u) { lx=dfn[u]; rx=dfn[u]+tsize[u]-1; return query(1); } else { int ret=2*1e9; for (int prex=pointer[u];prex;prex=edge[prex].pre) if (edge[prex].to!=anc[u]) { if (dfn[edge[prex].to]<=dfn[croot] && dfn[edge[prex].to]+tsize[edge[prex].to]-1>=dfn[croot]) { lx=1; rx=dfn[edge[prex].to]-1; if (rx>=lx) ret=min(ret,query(1)); lx=dfn[edge[prex].to]+tsize[edge[prex].to]; rx=tstamp; if (rx>=lx) ret=min(ret,query(1)); } } return ret; } } int main() { readx(nodenum); readx(opt); for (int i=1;i<nodenum;i++) { readx(fx); readx(tx); Insert(); } for (int i=1;i<=nodenum;i++) readx(nodev[i]); readx(croot); Fancy(1,1,0); Dreams(1,1); BuildTree(1,tstamp,1); for (int i=1;i<=opt;i++) { readx(typ); if (typ==1) readx(croot); else if (typ==2) { readx(ux); readx(vx); readx(val); upd_range(ux,vx); } else { readx(ux); printf("%d\n",solve(ux)); } } return 0; } |