首页 > 代码库 > SPOJ QTREE系列 树上分治问题。
SPOJ QTREE系列 树上分治问题。
375.Query on a tree 【QTREE】
有两个操作：
（1）修改第i条边的边权
（2）询问a到b路径上的边权最大值。
树链剖分入门题。树链剖分+线段树维护最大值。修改/查询均为O(log^2)。
很懒，没有写。
913.Query on a tree II 【QTREE2】
有两个操作：
（1）询问a到b的距离。
（2）询问a到b路径上的第k个点。
很容易想到倍增LCA。
路径上的第k个点，要么是a的第k个父亲，要么是b的第k‘个父亲，同样可以倍增实现。
询问都是O(logn)。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 #define MAXN 10010 8 #define MAXD 16 9 using namespace std;10 int v[MAXN*2],e[MAXN*2],next[MAXN*2],first[MAXN];11 int d[MAXN],p[MAXN][MAXD],dis[MAXN][MAXD];12 int n,tot;13 char op[5];14 15 void addedge(int x,int y,int z){16 v[++tot]=y;e[tot]=z;next[tot]=first[x];first[x]=tot;17 v[++tot]=x;e[tot]=z;next[tot]=first[y];first[y]=tot;18 }19 20 void dfs(int u,int fa,int dist){21 d[u]=d[fa]+1,p[u][0]=fa,dis[u][0]=dist;22 for(int i=1;i<MAXD;i++){23 p[u][i]=p[p[u][i-1]][i-1];24 dis[u][i]=dis[u][i-1]+dis[p[u][i-1]][i-1];25 }26 for(int i=first[u];i;i=next[i])27 if(v[i]!=fa)28 dfs(v[i],u,e[i]);29 }30 31 int lca(int x,int y){32 if(d[x]>d[y]) swap(x,y);33 int delta=d[y]-d[x];34 for(int i=0;i<MAXD;i++)35 if(delta&(1<<i))36 y=p[y][i];37 if(x==y) return x;38 for(int i=MAXD-1;i>=0;i--)39 if(p[x][i]!=p[y][i])40 x=p[x][i],y=p[y][i];41 return p[x][0];42 }43 44 int getdis(int x,int y){45 if(d[x]>d[y]) swap(x,y);46 int ret=0,delta=d[y]-d[x];47 for(int i=0;i<MAXD;i++)48 if(delta&(1<<i))49 ret+=dis[y][i],y=p[y][i];50 if(x==y) return ret;51 for(int i=MAXD-1;i>=0;i--)52 if(p[x][i]!=p[y][i]){53 ret+=dis[x][i],x=p[x][i];54 ret+=dis[y][i],y=p[y][i];55 }56 ret=ret+dis[x][0]+dis[y][0];57 return ret;58 }59 60 int getkthfa(int x,int k){61 for(int i=0;i<MAXD;i++)62 if(k&(1<<i))63 x=p[x][i];64 return x;65 }66 67 int getkth(int x,int y,int k){68 int t=lca(x,y);69 if(d[x]-d[t]>=k-1)70 return getkthfa(x,k-1);71 else72 return getkthfa(y,d[x]-d[t]+d[y]-d[t]+1-k); 73 }74 75 int main(){76 freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);77 int t;scanf("%d",&t);78 while(t--){79 scanf("%d",&n);80 memset(first,0,sizeof(first));81 tot=0;82 for(int i=1;i<n;i++){83 int x,y,z;84 scanf("%d%d%d",&x,&y,&z);85 addedge(x,y,z);86 }87 dfs(1,0,0);88 while(scanf("%s",op)!=EOF && op[1]!=‘O‘)89 if(op[0]==‘D‘){90 int a,b;scanf("%d%d",&a,&b); 91 printf("%d\n",getdis(a,b));92 }else{93 int a,b,k;scanf("%d%d%d",&a,&b,&k);94 printf("%d\n",getkth(a,b,k));95 }96 }97 return 0;98 }
| ID | DATE | PROBLEM | RESULT | TIME | MEM | LANG | |
|---|---|---|---|---|---|---|---|
| 12000885 | 2014-07-23 03:30:46 | Query on a tree II | accepted edit run | 0.61 | 4.4M | C++ 4.3.2 |
2789.Query on a tree again 【QTREE3】
有两个操作：
（1）单点颜色修改，黑变白，或者白变黑。
（2）询问1到v路径上，最先出现黑点的位置。
树链剖分肯定能做，我用的是LCT。
我们需要维护一段区间1-v上最先出现的黑点位置，即这条链中最上面的黑点。
等价于splay中最左边出现的黑点。很裸吧。
理论的修改/询问均为O(logn)，最好常数优化，我加了fread 25-->100！
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 #define MAXN 200000 8 using namespace std; 9 int n,q; 10 11 struct LinkCutTree{ 12 int ch[MAXN][2],col[MAXN],front[MAXN],f[MAXN],rev[MAXN]; 13 bool isroot(int x){ 14 return (!f[x]||ch[f[x]][0]!=x&&ch[f[x]][1]!=x); 15 } 16 void push_up(int x){ 17 if(!x) return; 18 int lc=ch[x][0],rc=ch[x][1]; 19 if(~front[lc]) front[x]=front[lc]; 20 else 21 if(col[x]) front[x]=x; 22 else 23 if(~front[rc]) front[x]=front[rc]; 24 else 25 front[x]=-1; 26 } 27 void push_down(int x){ 28 if(!x) return; 29 int lc=ch[x][0],rc=ch[x][1]; 30 if(rev[x]){ 31 swap(ch[x][0],ch[x][1]); 32 rev[lc]^=1;rev[rc]^=1; 33 rev[x]=0; 34 } 35 } 36 void rotate(int x,int t){ 37 if(isroot(x)) return; 38 int y=f[x]; 39 ch[y][t]=ch[x][!t];if(ch[x][!t]) f[ch[x][!t]]=y; 40 f[x]=f[y];if(f[y]){ 41 if(ch[f[y]][0]==y) ch[f[y]][0]=x; 42 if(ch[f[y]][1]==y) ch[f[y]][1]=x; 43 } 44 f[ch[x][!t]=y]=x;push_up(y); 45 } 46 void splay(int x){ 47 push_down(x); 48 while(!isroot(x)){ 49 int y=f[x];push_down(y);push_down(x); 50 rotate(x,ch[y][1]==x); 51 } 52 push_up(x); 53 } 54 void init(){ 55 memset(front,255,sizeof(front)); 56 } 57 void access(int v){ 58 for(int u=v,v=0;u;v=u,u=f[u]) splay(u),ch[u][1]=v; 59 } 60 void evert(int v){ 61 access(v);splay(v);rev[v]^=1; 62 } 63 int find_root(int v){ 64 access(v);splay(v);for(;ch[v][0];v=ch[v][0]);splay(v);return v; 65 } 66 void link(int u,int v){ 67 evert(u);f[u]=v; 68 } 69 void cut(int u,int v){ 70 evert(u);access(v);splay(v);f[u]=ch[v][0]=0; 71 } 72 void modify(int v){ 73 access(v);splay(v);col[v]^=1; 74 } 75 int query(int v){ 76 evert(1);access(v);splay(v);return front[v]; 77 } 78 }LCT; 79 80 char buf[8000000],*pt = buf,*o = buf; 81 inline int getint(){ 82 int f = 1,x = 0; 83 while((*pt != ‘-‘) && (*pt < ‘0‘ || *pt > ‘9‘)) pt ++; 84 if(*pt == ‘-‘) f = -1,pt ++; else x = *pt++ - 48; 85 while(*pt >= ‘0‘ && *pt <= ‘9‘) x = x * 10 + *pt ++ - 48; 86 return x * f; 87 } 88 89 90 int main(){ 91 freopen("input.txt","r",stdin);freopen("output.txt","w",stdout); 92 fread(buf,1,8000000,stdin); 93 n=getint(),q=getint(); 94 LCT.init(); 95 for(int i=1;i<n;i++){ 96 int x=getint(),y=getint(); 97 LCT.link(x,y); 98 } 99 while(q--){100 int op=getint(),v=getint();101 if(op==0) LCT.modify(v);102 else printf("%d\n",LCT.query(v));103 }104 return 0;105 }
| ID | DATE | PROBLEM | RESULT | TIME | MEM | LANG | |
|---|---|---|---|---|---|---|---|
| 12002267 | 2014-07-23 09:19:09 | Query on a tree again! | 100 edit run | 11.63 | 15M | C++ 4.3.2 |
2666.Query on a tree IV 【QTREE4】
同样是两个操作：
（1）单点颜色修改
（2）询问整棵树中，最远的白色两点的距离 <==>max{dist(a,b)},color[a]=color[b]=white.
公认的QTREE1-5中最繁琐的题目。我想练练手边分，树的边分应该是最难写的。
请教神犇，都称“珍惜生命，请用点分治” T T
这道题目用边分是很直观的。
每层找出一条中心边，删边，可以分成左右两个子树。
左右各维护一个大根堆，分别记录白点到子树根的距离。
ans=max{lc.ans,rc.ans,leftheap.top()+rightheap.top()+midlen}
（极限数据我用SET3.8s，用优先队列2.5s）
询问是O(1)，修改是O(log^2)。
补充边分的知识：
①树是菊花状，边分会退化。
可以试着加虚点。（这里是向jcvb学习的）遵循第二个儿子就加虚点的原则。
②有些有趣的性质。不难发现每个节点的度不大于3，或者说这就是棵二叉树！
实节点只在左儿子。
最重要的是，他不再是菊花了！
③dfs记录答案信息。点分/边分维护路径长度是可行的。
比如记下每个点到该层子树根的距离。总的空间是nlogn。
④拆掉每条边的估价和左右子树的大小有关。
dfs_size(),min{max{size[u],n-size[u]}}，可以找到中心边了。
⑤递归左右子树，回到③。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 #include<set> 8 #include<queue> 9 using namespace std; 10 11 #define MAXN 210000 12 #define MAXM 4000000 13 #define WHITE 1 14 #define BLACK 0 15 16 int V[MAXM],E[MAXM],NEXT[MAXM],FIR[MAXN]; int N; 17 int v[MAXN*2],e[MAXN*2],next[MAXN*2],pre[MAXN*2],fir[MAXN],ed[MAXN]; int n; 18 int col[MAXN],size[MAXN]; 19 int p,mi,midedge,tot; 20 21 char buf[8000000],*pt = buf,*o = buf; 22 int getint(){ 23 int f = 1,x = 0; 24 while((*pt != ‘-‘) && (*pt < ‘0‘ || *pt > ‘9‘)) pt ++; 25 if(*pt == ‘-‘) f = -1,pt ++; else x = *pt++ - 48; 26 while(*pt >= ‘0‘ && *pt <= ‘9‘) x = x * 10 + *pt ++ - 48; 27 return x * f; 28 } 29 char getch(){ 30 char ch; 31 while(*pt < ‘A‘ || *pt > ‘Z‘) pt ++; 32 ch=*pt;pt++; 33 return ch; 34 } 35 36 void ADD1(int x,int y,int z){ 37 V[tot]=y;E[tot]=z;NEXT[tot]=FIR[x];FIR[x]=tot;tot++; 38 } 39 40 void ADD(int x,int y,int z){ 41 V[tot]=y;E[tot]=z;NEXT[tot]=FIR[x];FIR[x]=tot;tot++; 42 V[tot]=x;E[tot]=z;NEXT[tot]=FIR[y];FIR[y]=tot;tot++; 43 } 44 45 void add(int x,int y,int z){ 46 v[tot]=y;e[tot]=z;next[tot]=fir[x];fir[x]=tot;tot++; 47 v[tot]=x;e[tot]=z;next[tot]=fir[y];fir[y]=tot;tot++; 48 } 49 50 void getpre(){ 51 memset(ed,255,sizeof(ed)); 52 for(int i=1;i<=n;i++) 53 for(int j=fir[i];~j;j=next[j]){ 54 pre[j]=ed[i]; 55 ed[i]=j; 56 } 57 } 58 59 void _delete(int x,int i){ 60 if(fir[x]==i) fir[x]=next[i]; else next[pre[i]]=next[i]; 61 if(ed[x]==i) ed[x]=pre[i]; else pre[next[i]]=pre[i]; 62 } 63 64 void init(){ 65 memset(FIR,255,sizeof(FIR));tot=0; 66 N=getint(); 67 for(int i=1;i<N;i++){ 68 int x=getint(),y=getint(),z=getint(); 69 ADD(x,y,z); 70 } 71 } 72 73 void check(int u,int fa){ 74 int father=0; 75 for(int i=FIR[u];~i;i=NEXT[i]) 76 if(V[i]!=fa) 77 if(father==0){ 78 add(u,V[i],E[i]); 79 father=u; 80 check(V[i],u); 81 }else{ 82 ++n;col[n]=BLACK; 83 add(father,n,0);add(n,V[i],E[i]); 84 father=n; 85 check(V[i],u); 86 } 87 } 88 89 void rebuild(){ 90 memset(fir,255,sizeof(fir));tot=0; 91 n=N; 92 for(int i=1;i<=n;i++) col[i]=WHITE; 93 check(1,0); 94 getpre(); 95 memset(FIR,255,sizeof(FIR));tot=0; 96 } 97 98 struct point{ 99 int dist,id;100 bool operator<(const point&b)const{101 return dist<b.dist;102 }103 };104 105 struct node{106 int rt,midlen,ans;107 int lc,rc;108 priority_queue<point>Q;109 }T[MAXN*4];110 111 int cnt=0;112 113 void dfs_size(int u,int fa,int dist){114 ADD1(u,p,dist);if(col[u])T[p].Q.push((point){dist,u});115 size[u]=1;116 for(int i=fir[u];~i;i=next[i])117 if(v[i]!=fa){118 dfs_size(v[i],u,dist+e[i]);119 size[u]+=size[v[i]];120 }121 }122 123 void dfs_midedge(int u,int code){124 if(max(size[u],size[T[p].rt]-size[u])<mi){125 mi=max(size[u],size[T[p].rt]-size[u]);126 midedge=code;127 }128 for(int i=fir[u];~i;i=next[i])129 if(i!=(code^1))130 dfs_midedge(v[i],i);131 }132 133 void push_up(int p){134 T[p].ans=-1;135 while(!T[p].Q.empty()&&(col[T[p].Q.top().id]==0)) T[p].Q.pop();136 int lc=T[p].lc,rc=T[p].rc;137 if(lc==0&&rc==0){138 if(col[T[p].rt]) T[p].ans=0;139 }else{140 if(T[lc].ans>T[p].ans) T[p].ans=T[lc].ans;141 if(T[rc].ans>T[p].ans) T[p].ans=T[rc].ans;142 if(!T[lc].Q.empty()&&!T[rc].Q.empty())143 T[p].ans=max(T[lc].Q.top().dist+T[rc].Q.top().dist+T[p].midlen,T[p].ans);144 }145 }146 147 void dfs(int pt,int u){148 T[pt].rt=u;149 p=pt;dfs_size(u,0,0);150 midedge=-1;mi=n;dfs_midedge(u,-1);151 if(~midedge){152 int p1=v[midedge],p2=v[midedge^1];153 T[pt].midlen=e[midedge];154 _delete(p1,midedge^1);155 _delete(p2,midedge);156 dfs(T[pt].lc=++cnt,p1);157 dfs(T[pt].rc=++cnt,p2); 158 }159 push_up(pt);160 }161 162 void change(int x){163 col[x]^=1;164 if(col[x]==BLACK)165 for(int i=FIR[x];~i;i=NEXT[i])166 push_up(V[i]);167 else168 for(int i=FIR[x];~i;i=NEXT[i]){169 T[V[i]].Q.push((point){E[i],x});170 push_up(V[i]);171 }172 }173 174 175 void solve(){176 int x;char op;177 int q=getint();178 while(q--){179 op=getch();180 if(op==‘A‘)181 if(~T[1].ans)182 printf("%d\n",T[1].ans);183 else184 puts("They have disappeared.");185 else{186 x=getint();187 change(x);188 }189 }190 }191 192 int main(){193 fread(buf,1,8000000,stdin);194 init();195 rebuild();196 dfs(cnt=1,1);197 solve();198 return 0;199 }
| ID | DATE | PROBLEM | RESULT | TIME | MEM | LANG |
|---|---|---|---|---|---|---|
| 12016831 | 2014-07-25 10:32:18 | Query on a tree IV | accepted | 10.42 | 101M | C++ 4.3.2 |
2939.Query on a tree V 【QTREE5】
两个操作：
（1）单点颜色修改
（2）给定点v，询问最近的白点（可能包括本身）的距离。
实际上是QTREE4的弱化版，于是这题就写点分了。
每层有若干个重心。
每个重心弄个堆，维护子树中的白色节点到其距离的最小值。
询问时，访问点v所在的所有重心I，answer=min{heapI.top()+dis(v,I)} v∈I.
修改/询问都是O(logn)。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 #include<queue> 8 using namespace std; 9 10 #define INF 0x3f3f3f3f 11 #define MAXN 400010 12 #define MAXM 3000010 13 #define BLACK 0 14 #define WHITE 1 15 int V[MAXM],E[MAXM],NEXT[MAXM],FIR[MAXN]; 16 int v[MAXN],e[MAXN],next[MAXN],fir[MAXN]; 17 int col[MAXN],size[MAXN],ma[MAXN],vis[MAXN]; 18 int n,tot;int mi,root,rt; 19 20 struct point{ 21 int dist,id; 22 bool operator<(const point&b)const{ 23 return dist>b.dist; 24 } 25 }; 26 priority_queue<point>Q[MAXN]; 27 28 char buf[10000000],*pt = buf,*o = buf; 29 inline int getint(){ 30 int f = 1,x = 0; 31 while((*pt != ‘-‘) && (*pt < ‘0‘ || *pt > ‘9‘)) pt ++; 32 if(*pt == ‘-‘) f = -1,pt ++; else x = *pt++ - 48; 33 while(*pt >= ‘0‘ && *pt <= ‘9‘) x = x * 10 + *pt ++ - 48; 34 return x * f; 35 } 36 37 void ADD(int x,int y,int z){ 38 V[tot]=y;E[tot]=z;NEXT[tot]=FIR[x];FIR[x]=tot;tot++; 39 } 40 41 void addedge(int x,int y){ 42 v[tot]=y;next[tot]=fir[x];fir[x]=tot;tot++; 43 v[tot]=x;next[tot]=fir[y];fir[y]=tot;tot++; 44 } 45 46 void init(){ 47 memset(fir,255,sizeof(fir));tot=0; 48 n=getint(); 49 for(int i=1;i<n;i++){ 50 int x=getint(),y=getint(); 51 addedge(x,y); 52 } 53 memset(FIR,255,sizeof(FIR));tot=0; 54 } 55 56 void dfssize(int u,int fa){ 57 size[u]=1;ma[u]=0; 58 for(int i=fir[u];~i;i=next[i]) 59 if(v[i]!=fa&&!vis[v[i]]){ 60 dfssize(v[i],u); 61 size[u]+=size[v[i]]; 62 if(size[v[i]]>ma[u]) ma[u]=size[v[i]]; 63 } 64 } 65 66 void dfsroot(int u,int fa){ 67 if(size[rt]-size[u]>ma[u]) ma[u]=size[rt]-size[u]; 68 if(ma[u]<mi) mi=ma[u],root=u; 69 for(int i=fir[u];~i;i=next[i]) 70 if(v[i]!=fa&&!vis[v[i]]) 71 dfsroot(v[i],u); 72 } 73 74 void dfsdis(int u,int fa,int dis){ 75 ADD(u,root,dis); 76 for(int i=fir[u];~i;i=next[i]) 77 if(v[i]!=fa&&!vis[v[i]]) 78 dfsdis(v[i],u,dis+1); 79 } 80 81 void dfs(int u){ 82 mi=n,rt=u;dfssize(u,0);dfsroot(u,0); 83 dfsdis(root,0,0); 84 vis[root]=1; 85 for(int i=fir[root];~i;i=next[i]) 86 if(!vis[v[i]]) 87 dfs(v[i]); 88 } 89 90 void modify(int x){ 91 col[x]^=1; 92 if(col[x]==WHITE) 93 for(int i=FIR[x];~i;i=NEXT[i]) 94 Q[V[i]].push((point){E[i],x}); 95 } 96 97 int query(int x){ 98 int ret=INF; 99 for(int i=FIR[x];~i;i=NEXT[i]){100 while(!Q[V[i]].empty()&&(col[Q[V[i]].top().id]==BLACK)) Q[V[i]].pop();101 if(!Q[V[i]].empty()) ret=min(Q[V[i]].top().dist+E[i],ret);102 }103 return ret<INF?ret:-1;104 }105 106 void solve(){107 int q=getint();108 int op,x;109 while(q--){110 op=getint(),x=getint();111 if(op==0)112 modify(x);113 else114 printf("%d\n",query(x));115 }116 }117 118 119 int main(){120 fread(buf,1,10000000,stdin);121 init();122 dfs(1);123 solve();124 return 0;125 }
| ID | DATE | PROBLEM | RESULT | TIME | MEM | LANG | |
|---|---|---|---|---|---|---|---|
| 12018865 | 2014-07-25 16:37:48 | Query on a tree V | accepted edit run | 6.36 | 95M | C++ 4.3.2 |
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。