375.QTREE
给你一棵n个点$n-1$条边的树，支持修改一条边的边权、查询两点之间路径上的最大边权。
树链剖分+线段树基础题
code:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int H[10005],X[20005],P[20005],tot, w[20005],E[20005],num[20005];
inline void add(int x,int y,int z,int no){
P[++tot]=y;X[tot]=H[x];H[x]=tot;E[tot]=z;num[tot]=no;
}
int mx[10005<<2];
int to[10005],tt,siz[10005],son[10005],top[10005],dep[10005],f[10005],tim;
void dfs1(int x,int fa){
siz[x]=1;son[x]=0;top[x]=0;
int mx=0;
for(int i=H[x];i;i=X[i]){
if(P[i]==fa) continue;
f[P[i]]=x;
dep[P[i]]=dep[x]+1;
w[P[i]]=E[i];
to[num[i]]=P[i];
dfs1(P[i],x);
siz[x]+=siz[P[i]];
if(siz[P[i]]>mx){
mx=siz[P[i]];
son[x]=P[i];
}
}
}
void dfs2(int x,int fa){
if(!top[x]) top[x]=x;
num[x]=++tim;
E[tim]=w[x];
if(son[x])top[son[x]]=top[x],dfs2(son[x],x);
for(int i=H[x];i;i=X[i]){
if(P[i]!=son[x]&&P[i]!=fa){
dfs2(P[i],x);
}
}
}
int _c,_l,_r;
void ask(int o,int l,int r){
if(_l<=l&&r<=_r){
_c=max(mx[o],_c);
return ;
}else{
int mid=(l+r)>>1;
if(_l<=mid) ask(o<<1,l,mid);
if(_r>mid) ask(o<<1|1,mid+1,r);
}
}
int ask(int l,int r){
_c=0;
_l=l,_r=r;
ask(1,1,n);
return _c;
}
int Ask(int a,int b){
int ret=0;
while(top[a]!=top[b]){
int x=top[a],y=top[b];
if(dep[x]<dep[y]) swap(x,y),swap(a,b);
ret=max(ask(num[x],num[a]),ret);
a=f[x];
}
if(a!=b){
if(dep[a]>dep[b]) swap(a,b);
ret=max(ret,ask(num[a]+1,num[b]));
}
return ret;
}
char s[50];
void change(int o,int l,int r,int p,int k){
if(l==r){
mx[o]=k;
}else{
int mid=(l+r)>>1;
if(p<=mid) change(o<<1,l,mid,p,k);
else change(o<<1|1,mid+1,r,p,k);
mx[o]=max(mx[o<<1],mx[o<<1|1]);
}
}
void bd(int o,int l,int r){
if(l==r){
mx[o]=E[l];
}else{
int mid=(l+r)>>1;
bd(o<<1,l,mid);
bd(o<<1|1,mid+1,r);
mx[o]=max(mx[o<<1],mx[o<<1|1]);
}
}
int main(){
scanf("%d",&tt);
while(tt--){
tim=tot=0;
memset(H,0,sizeof H);
scanf("%d",&n);
for(int i=1,a,b,c;i<n;i++){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c,i);
add(b,a,c,i);
}
dep[1]=1;
dfs1(1,-1);
dfs2(1,-1);
bd(1,1,n);
int a,b;
while(scanf("%s",s),s[0]!='D'){
if(s[0]=='Q'){
scanf("%d%d",&a,&b);
printf("%d\n",Ask(a,b));
}else{
scanf("%d%d",&a,&b);
change(1,1,n,num[to[a]],b);
}
}
}
return 0;
}
913.QTREE2
一棵树，两个操作。
1.询问a到b的最短路。
2.询问a到b的最短路上第k个点是啥。
倍增或者树链剖分。
code：
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int tt;
int n;
typedef long long LL;
LL d[10005][16];
int f[10005][16],dep[10005];
int H[10005],X[20005],P[20005],tot,E[20005];
inline void add(int x,int y,int z){
P[++tot]=y;X[tot]=H[x];H[x]=tot;E[tot]=z;
}
void dfs(int x){
dep[x]=dep[f[x][0]]+1;
for(int i=H[x];i;i=X[i]){
if(P[i]!=f[x][0]){
f[P[i]][0]=x;
d[P[i]][0]=E[i];
dfs(P[i]);
}
}
}
int lg;
char s[50];
LL dist(int x,int y){
LL ret=0;
if(dep[x]<dep[y]) swap(x,y);
for(int i=lg;i>=0;i--) if(dep[f[x][i]]>=dep[y]) ret+=d[x][i],x=f[x][i];
if(x==y) return ret;
for(int i=lg;i>=0;i--){
if(f[x][i]!=f[y][i]){
ret+=d[x][i]+d[y][i];
x=f[x][i];
y=f[y][i];
}
}
return ret+d[x][0]+d[y][0];
}
int ask(int x,int y,int k){
int lca=0,xx=x,yy=y;
if(dep[x]<dep[y]) swap(x,y);
for(int i=lg;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
if(x==y) lca=x;
for(int i=lg;i>=0;i--){
if(f[x][i]!=f[y][i]){
x=f[x][i];
y=f[y][i];
}
}
if(!lca) lca=f[x][0];
x=xx,y=yy;
if(-dep[lca]+dep[x]+1<k){
k=-dep[lca]+dep[x]+1-dep[lca]+dep[y]-k+1;
x=y;
}
k--;
for(int i=0;i<=lg;i++) if((k>>i)&1) x=f[x][i];
return x;
}
int main(){
scanf("%d",&tt);
while(tt--){
tot=0;memset(H,0,sizeof H);
memset(f,0,sizeof f);
memset(d,0,sizeof d);
memset(dep,0,sizeof dep);
scanf("%d",&n);
for(int i=1,x,y,z;i<n;i++){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dfs(1);
for(lg=0;(1<<lg)<=n;lg++) ;lg--;
for(int j=0;j<=lg;j++){
for(int i=1;i<=n;i++){
if(f[i][j]){
f[i][j+1]=f[f[i][j]][j];
d[i][j+1]=d[i][j]+d[f[i][j]][j];
}
}
}
int a,b,k;
while(scanf("%s",s),s[1]!='O'){
if(s[0]=='D'){
scanf("%d%d",&a,&b);
printf("%lld\n",dist(a,b));
}else{
scanf("%d%d%d",&a,&b,&k);
printf("%d\n",ask(a,b,k));
}
}
}
return 0;
}
2798.QTREE3
(partial)
给你一棵树，root是1，开始所有点是白色。
有两个操作：
1.把一个点v由白变黑，有黑边白。
2.问从root到点v第一个黑点是哪个，没有输出-1.
树链剖分+线段树。
code:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,q;
int H[100005],X[200005],P[200005],tot;
inline void add(int x,int y){
P[++tot]=y;X[tot]=H[x];H[x]=tot;
}
int siz[100005],top[100005],son[100005],to[100005],tim,f[100005],p[100005];
int sum[100005*4];
void dfs1(int x,int fa){
siz[x]=1;
int mx=0;
for(int i=H[x];i;i=X[i]){
if(P[i]!=fa){
f[P[i]]=x;
dfs1(P[i],x);
siz[x]+=siz[P[i]];
if(siz[P[i]]>mx){
mx=siz[P[i]];
son[x]=P[i];
}
}
}
}
void dfs2(int x,int fa){
if(!top[x]) top[x]=x;
to[x]=++tim;
p[tim]=x;
if(son[x]){
top[son[x]]=top[x];
dfs2(son[x],x);
}
for(int i=H[x];i;i=X[i]){
if(P[i]!=fa&&P[i]!=son[x]){
dfs2(P[i],x);
}
}
}
int _l,_r,_c;
void ask(int o,int l,int r){
if(!sum[o]) return;
if(_l<=l&&r<=_r){
_c+=sum[o];
}else{
int mid=(l+r)>>1;
if(_l<=mid) ask(o<<1,l,mid);
if(_r>mid) ask(o<<1|1,mid+1,r);
}
}
int ask(int l,int r){
if(l>r) return 0;
_c=0,_l=l,_r=r;
ask(1,1,n);
return _c;
}
void change(int o,int l,int r,int p){
if(l==r){
sum[o]^=1;
}else{
int mid=(l+r)>>1;
if(p<=mid) change(o<<1,l,mid,p);
else change(o<<1|1,mid+1,r,p);
sum[o]=sum[o<<1]+sum[o<<1|1];
}
}
int ask(int k){
int o=1,l=1,r=n;
while(l!=r){
int mid=(l+r)>>1;
if(sum[o<<1]>=k) o<<=1,r=mid;
else k-=sum[o<<1],o=o<<1|1,l=mid+1;
}
return p[l];
}
int Ask(int x){
int last=0;
while(1){
//topx..x
if(ask(to[top[x]],to[x])>0) last=x;
if(top[x]==1) break;
else x=f[top[x]];
}
if(!last) return -1;
int sum=ask(1,to[top[last]]-1);
return ask(sum+1);
}
int getint(){
static char c;
static int x;
while(c=getchar(),c<'0'||c>'9');
x=c-'0';
while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';
return x;
}
int main(){
//scanf("%d%d",&n,&q);
n=getint();
q=getint();
for(int i=1,x,y;i<n;i++){
x=getint();y=getint();
add(x,y);add(y,x);
}
dfs1(1,0);dfs2(1,0);
for(int i=0,x,y;i<q;i++){
x=getint();y=getint();
if(x){
printf("%d\n",Ask(y));
}else{
change(1,1,n,to[y]);
}
}
return 0;
}
1487.PT07J
Another QTREE3
给你一个有标号的有根树。
q(x,k) 询问在x的子树中，第k大的标号是哪个点。
首先离散化
树上k大，用dfs序+主席树维护。
code:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int w[100005],H[100005],X[200005],P[200005],tot,to[100005],l[100005],r[100005],root[100005];
int sum[100005*50],ls[100005*50],rs[100005*50];
inline void add(int x,int y){
P[++tot]=y;X[tot]=H[x];H[x]=tot;
}
int n,cc,m;
int tim;
int add(int o,int l,int r,int pos){
int p=++cc;
sum[p]=sum[o]+1;
if(l==r){
return p;
}else{
int mid=(l+r)>>1;
if(pos<=mid){
ls[p]=add(ls[o],l,mid,pos);
rs[p]=rs[o];
}else{
ls[p]=ls[o];
rs[p]=add(rs[o],mid+1,r,pos);
}
}
return p;
}
void dfs(int x,int fa){
l[x]=++tim;
root[tim]=add(root[tim-1],1,n,w[x]);
for(int i=H[x];i;i=X[i]){
if(P[i]==fa) continue;
dfs(P[i],x);
}
r[x]=tim;
}
int ask(int o1,int o2,int l,int r,int k){
if(l==r){
return l;
}else{
int mid=(l+r)>>1;
int tmp=sum[ls[o1]]-sum[ls[o2]];
if(tmp>=k){
return ask(ls[o1],ls[o2],l,mid,k);
}else return ask(rs[o1],rs[o2],mid+1,r,k-tmp);
}
}
int getint(){
static char c;
static int x;
while(c=getchar(),c<'0'||c>'9');
x=c-'0';
while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';
return x;
}
int main(){
n=getint();
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
to[i]=w[i];
}
sort(to+1,to+n+1);
for(int i=1;i<=n;i++) w[i]=lower_bound(to+1,to+n+1,w[i])-to;
for(int i=1;i<=n;i++) to[w[i]]=i;
for(int i=1,x,y;i<n;i++){
x=getint();y=getint();
add(x,y);add(y,x);
}
dfs(1,0);
m=getint();
for(int i=0,x,k;i<m;i++){
x=getint();k=getint();
printf("%d\n",to[ask(root[r[x]],root[l[x]-1],1,n,k)]);
}
return 0;
}
2666.QTREE4
代填。
orz: http://www.cnblogs.com/fullpower/p/3869547.html