edward_mj

【题目地址】https://www.spoj.pl/problems/QTREE3/

【题目大意】
给定一棵树，一开始所有点都是白色的。
给定两个操作：
0 x：把点x变色（本来是白色变成黑色，本来是黑色变成白色）
1 x：求从结点1到点x的路径上，第一个黑色的点是哪一个？如果没有，输出-1。
【算法分析】
树链剖分例题(比本文详细)：http://hi.baidu.com/edwardmj/blog/item/2894235220a1be501038c2c9.html
首先显然把结点1当做根变成有根树。
轻重边剖分，然后都于每个重路径建立一棵线段树，然后对于操作0，就把线段树里对应那个点取反即可。
然后对于操作1，就从点x一直向父亲走，遇到重路径就跳到重路径的起始端，并用线段树取最小值，遇到轻边的话就直接走。
【其它】
跑了12s+。。。。果然我写的程序总是比较慢= =
【CODE】
#include #include #include const int N=100005;
const int INF=1000000000;
struct gtp{int x,y,next,op,inlist;}g[N*2];
struct TT{int l,r,zz;}tr[N*8];
int n,m,e,times,tot,ct,ans;
int ls[N],list[N],fa[N],Size[N],myheavy[N],black[N];
int color[N],cst[N];

void addedge(int x,int y){
g[++e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e; g[e].op=e+1;
g[++e].x=y; g[e].y=x; g[e].next=ls[y]; ls[y]=e; g[e].op=e-1;
}

void input(){
scanf("%d%d",&n,&m);
for (int i=1,x,y;i scanf("%d%d",&x,&y);
addedge(x,y);
}
}

void predfs(int p){
Size[p]=times++;
for (int t=ls[p];t;t=g[t].next)
if (!fa[p] || t!=g[fa[p]].op){
fa[g[t].y]=t;
predfs(g[t].y);
}
Size[p]=times-Size[p];
}

void dfs(int p){
int mt,mm=-INF;
for (int t=ls[p];t;t=g[t].next)
if ((!fa[p] || t!=g[fa[p]].op) && Size[g[t].y]>mm){
mm=Size[g[t].y];
mt=t;
}
if (mm==-INF) return;
myheavy[p]=mt;
list[++tot]=mt;
g[mt].inlist=tot;
dfs(g[mt].y);
for (int t=ls[p];t;t=g[t].next)
if ((!fa[p] || t!=g[fa[p]].op) && t!=mt)
dfs(g[t].y);
}

void draw_color(){
ct=color[1]=cst[1]=1;
for (int i=2;i<=tot;i++){
if (g[list[i-1]].y!=g[list[i]].x) cst[++ct]=i;
color[i]=ct;
}
}

void build(int p,int l,int r){
tr[p].l=l; tr[p].r=r; tr[p].zz=0;
if (l==r) return;
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
}

void change(int p,int x){
if (tr[p].l==tr[p].r){
if (tr[p].zz) tr[p].zz=0;
else tr[p].zz=g[list[x]].x;
return;
}
int mid=(tr[p].l+tr[p].r)/2;
if (x<=mid) change(p*2,x);
else change(p*2+1,x);
if (tr[p*2].zz) tr[p].zz=tr[p*2].zz;
else tr[p].zz=tr[p*2+1].zz;
}

void Get_zz(int p,int l,int r){
if (l<=tr[p].l && tr[p].r<=r){
if (tr[p].zz) ans=tr[p].zz;
return;
}
int mid=(tr[p].l+tr[p].r)/2;
if (r>mid) Get_zz(p*2+1,l,r);
if (l<=mid) Get_zz(p*2,l,r);
}

void Try(int x){
if (black[x]) ans=x;
if (x==1) return;
if (!g[fa[x]].inlist) Try(g[fa[x]].x);
else{
Get_zz(1,cst[color[g[fa[x]].inlist]],g[fa[x]].inlist);
Try(g[list[cst[color[g[fa[x]].inlist]]]].x);
}
}

void deal(){
for (int op,x,i=1;i<=m;i++){
scanf("%d%d",&op,&x);
if (op==0){
black[x]^=1;
if (myheavy[x]) change(1,g[myheavy[x]].inlist);
}else{
ans=0;
Try(x);
if (ans) printf("%dn",ans);
else printf("-1n");
}
}
}

int main(){
input();
predfs(1);
dfs(1);
draw_color();
build(1,1,tot);
deal();
}

【题目大意】
给出一棵带权的树。有两种询问。
1、问节点a到结点b路径的权和。
2、问节点a到结点b路径中第k个点是哪个。
【算法分析】
直接搞个RMQ来算LCA。
对于询问1，轻松得出ans=dist[a]+dist[b]-dist[LCA(a,b)]
对于询问2，按照a和b到LCA(a,b)的距离，可以判断他在LCA到a的链上还是到b的链上。
进一步转化为询问(x,y)：x上根走y步到达哪一个节点。
我们先把询问都放进链表里，然后一次记录路径的DFS，轻松解决。
【其他】1A
【CODE】
#include #include #include const int N=10005;
const int QQ=1000000;
struct edge{int y,w;edge *next;}space[N*2],*ls[N],Qspace[QQ],*Qls[N];
int n,e,Tc,Qe,tot,Qn;
int dist[N],dep[N],list[N*2],R[N],ans[QQ];
int rmq_node[17][N*2],rmq_dep[17][N*2],lg[N*2];

void addedge(int x,int y,int w){
space[++e].y=y; space[e].w=w;
space[e].next=ls[x]; ls[x]=&space[e];
}

void predfs(int p,int fa){
list[++tot]=p;
R[p]=tot;
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa){
dist[t->y]=dist[p]+t->w;
dep[t->y]=dep[p]+1;
predfs(t->y,p);
list[++tot]=p;
}
}

void buildrmq(){
for (int i=1;i<=tot;i++){
rmq_node[0][i]=list[i];
rmq_dep[0][i]=dep[list[i]];
}
for (int k=1;1< for (int i=1;i+(1< if (rmq_dep[k-1][i] rmq_dep[k][i]=rmq_dep[k-1][i];
rmq_node[k][i]=rmq_node[k-1][i];
}else{
rmq_dep[k][i]=rmq_dep[k-1][i+(1< rmq_node[k][i]=rmq_node[k-1][i+(1< }
}

void init(){
e=0; memset(ls,0,sizeof(ls));
Qn=0; Qe=0; memset(Qls,0,sizeof(Qls));
scanf("%d",&n);
for (int i=1,x,y,w;i scanf("%d%d%d",&x,&y,&w);
addedge(x,y,w);
addedge(y,x,w);
}
dist[1]=0; dep[1]=0; tot=0;
predfs(1,0);
buildrmq();
}

void addquestion(int x,int y){
Qspace[++Qe].y=y; Qspace[Qe].next=Qls[x]; Qls[x]=&Qspace[Qe];
Qspace[Qe].w=Qn;
}

int LCA(int l,int r){
if (l>r){
int tmp=l; l=r; r=tmp;
}
int k=lg[r-l+1];
if (rmq_dep[k][l] return rmq_node[k][l];
else
return rmq_node[k][r-(1<}

void build_question(){
char op[100];
int x,y,k,p;
for (Qn=1;;Qn++){
scanf("%s",op+1);
if (op[1]==’D’ && op[2]==’O’){
Qn–;
break;
}
if (op[1]==’D’){
scanf("%d%d",&x,&y);
p=LCA(R[x],R[y]);
ans[Qn]=dist[x]-2*dist[p]+dist[y];
}
else{
scanf("%d%d%d",&x,&y,&k);
p=LCA(R[x],R[y]);
if (dep[x]-dep[p]+1==k) ans[Qn]=p;
else if (k else addquestion(y,dep[y]-dep[p]-(k-(dep[x]-dep[p]+1)));
}
}
}

void solve(int p,int fa){
list[++tot]=p;
for (edge *q=Qls[p];q;q=q->next)
ans[q->w]=list[tot-q->y];
for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa) solve(t->y,p);
tot–;
}

int main(){
lg[1]=0;
for (int i=2;i lg[i]=lg[i-1];
if (1< }
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
init();
build_question();
tot=0;
solve(1,0);
for (int j=1;j<=Qn;j++) printf("%dn",ans[j]);
}
}