[BZOJ 3306]树
这个题其他操作都不难（DFS序+线段树水过），就是换根有点头疼……直接做的话要TopTree吧。
不过我们考虑用DFS序+线段树的“偷懒”做法。每次查询的时候考虑当前的根，如果这个根最初不在x的子树中，那么对目前的查询值没有影响；如果就是x，那么整个树都是x的子树；如果是x的某个后代，那么整个树里除了他的后代所在额这颗子树以外的所有部分全部变成了x的子树（试着翻转一下就明白了）。判断后代祖先以及在哪个子树这些东西可以用倍增LCA高效实现，问题就这样简单了。
代码：
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 | /************************************************************** Problem: 3306 User: danihao123 Language: C++ Result: Accepted Time:2308 ms Memory:17544 kb****************************************************************/ #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn=100005;const int maxnode=maxn*4;const int INF=0x7fffffff;#define SEG_STD int o,int L,int R#define MAKE_MID int M=L+(R-L)/2// #define MAKE_CLD int lc=o<<1,rc=o<<1|1#define LCH o<<1,L,M#define RCH o<<1|1,M+1,Rint n;int minv[maxnode];int A[maxn];void maintain(int o){ minv[o]=min(minv[o<<1],minv[o<<1|1]);}void build_tree(SEG_STD){ if(L==R){ minv[o]=A[L]; }else{ MAKE_MID; build_tree(LCH); build_tree(RCH); maintain(o); }}int ql,qr;int query(SEG_STD){ if(ql<=L && R<=qr){ return minv[o]; }else{ MAKE_MID; int ans=INF; if(ql<=M) ans=min(ans,query(LCH)); if(qr>M) ans=min(ans,query(RCH)); return ans; }}int p,v;void update(SEG_STD){ if(L==R){ minv[o]=v; }else{ MAKE_MID; if(p<=M) update(LCH); else update(RCH); maintain(o); }}inline int query(int l,int r){ if(l<1 || l>n || r<1 || r>n) return INF; ql=l; qr=r; return query(1,1,n);}inline void update(int pos,int value){ p=pos; v=value; update(1,1,n);} int first[maxn];int next[maxn],to[maxn];int graph_cnt=0;inline void AddEdge(int u,int v){ graph_cnt++; next[graph_cnt]=first[u]; first[u]=graph_cnt; to[graph_cnt]=v;} int d[maxn];int tid[maxn];int anc[maxn][19],dep[maxn];int siz[maxn];int dfs_clk=0;void dfs(int x,int fa,int depth){ dfs_clk++; tid[x]=dfs_clk; A[dfs_clk]=d[x]; anc[x][0]=fa; dep[x]=depth; siz[x]=1; int i; for(i=first[x];i;i=next[i]){ dfs(to[i],x,depth+1); siz[x]+=siz[to[i]]; }}void process(){ register int i,j; for(j=1;(1<<j)<n;j++) for(i=1;i<=n;i++) if(anc[i][j-1]!=-1) anc[i][j]=anc[anc[i][j-1]][j-1];}int root;bool isAnc(int x){ register int p=root,j; if(dep[p]<dep[x]) return false; for(j=18;j>=0;j--) if(dep[p]-(1<<j)>=dep[x] && anc[p][j]!=-1) p=anc[p][j]; return p==x;}int findAnc(int x,int y){ register int j; for(j=18;j>=0;j--) if(dep[y]-dep[x]-(1<<j)>0 && anc[y][j]!=-1) y=anc[y][j]; return y;} int getAns(int x){ if(x==root){ return query(1,n); }else{ if(isAnc(x)){ register int t=findAnc(x,root); register int l=tid[t],r=tid[t]+siz[t]-1; return min(query(1,l-1),query(r+1,n)); }else{ return query(tid[x],tid[x]+siz[x]-1); } }} int main(){ int q,x,f; register int i; char buf[3]; scanf("%d%d",&n,&q); for(i=1;i<=n;i++){ scanf("%d%d",&f,&d[i]); if(!f){ root=i; }else{ AddEdge(f,i); } } memset(anc,-1,sizeof(anc)); dfs(root,-1,0); process(); build_tree(1,1,n); while(q--){ scanf("%s%d",buf,&x); if(buf[0]=='V'){ scanf("%d",&f); update(tid[x],f); }else{ if(buf[0]=='Q'){ printf("%d\n",getAns(x)); }else{ root=x; } } } return 0;} |
[BZOJ 2588]Count on a tree
泥萌感觉我还能说什么……
这题就是DFS序套主席树，顺便带上倍增LCA，但有两大坑点：
- 存放数据不一定要用long long，但输入必须要。
- 输出数据蛋疼，最后一行行末没回车。
代码：
