生活随笔
收集整理的這篇文章主要介紹了
SPOJ - QTREE3Query on a tree again!——树链剖分
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
【題目描述】
SPOJ - QTREE3Query on a tree again!
【題目分析】
題目要求是輸出從111到xxx的路徑上遇到的第一個(gè)黑色的點(diǎn)。我們可以用樹鏈剖分（不了解的同學(xué)請出門左拐，詳見樹鏈剖分入門）
我們用線段樹維護(hù)每個(gè)區(qū)間第一次遇到黑點(diǎn)的位置，這樣訪問出的點(diǎn)同樣是從1開始路徑上的第一個(gè)點(diǎn)。因?yàn)槲覀兛偸菑母?jié)點(diǎn)1開始，我們在訪問的時(shí)候從后往前每次訪問重鏈時(shí)在線段樹上都是一段連續(xù)的區(qū)間，因此在映射數(shù)組的位置越靠前則在路徑上越靠前
【AC代碼】
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>using namespace std
;const int MAXN
=100005;
vector
<int>g
[MAXN
];
int fa
[MAXN
],A
[MAXN
],color
[MAXN
],pos
[MAXN
],siz
[MAXN
],son
[MAXN
],h
[MAXN
],top
[MAXN
],re
[MAXN
];
int cnt
=0,n
,m
;
int Min
[MAXN
<<2];void dfs1(int u
,int f
)
{int i
,v
;siz
[u
]=1;son
[u
]=0;fa
[u
]=f
;h
[u
]=h
[f
]+1;for(i
=0;i
<g
[u
].size();i
++){v
=g
[u
][i
];if(v
!=f
){dfs1(v
,u
);siz
[u
]+=siz
[v
];if(siz
[son
[u
]]<siz
[v
]) son
[u
]=v
;}}
}
void dfs2(int u
,int f
,int k
)
{int i
,v
;top
[u
]=k
;pos
[u
]=++cnt
;re
[cnt
]=u
;if(son
[u
]) dfs2(son
[u
],u
,k
);for(i
=0;i
<g
[u
].size();i
++){v
=g
[u
][i
];if(v
!=f
&&v
!=son
[u
]) dfs2(v
,u
,v
);}
}void build(int k
,int l
,int r
)
{if(l
==r
){Min
[k
]=INT_MAX
;return; }int mid
=(l
+r
)>>1;build(k
<<1,l
,mid
);build(k
<<1|1,mid
+1,r
);Min
[k
]=min(Min
[k
<<1],Min
[k
<<1|1]);
}void update(int k
,int l
,int r
,int x
,int color
)
{if(l
==r
){if(color
==1)Min
[k
]=l
;elseMin
[k
]=INT_MAX
;return;}int mid
=(l
+r
)/2;if(x
<=mid
) update(k
<<1,l
,mid
,x
,color
);else update(k
<<1|1,mid
+1,r
,x
,color
);Min
[k
]=min(Min
[k
<<1],Min
[k
<<1|1]);
}int QueryMin(int k
,int l
,int r
,int L
,int R
)
{if(L
<=l
&& r
<=R
) return Min
[k
];int mid
=(l
+r
)/2;int ret
=INT_MAX
;if(L
<=mid
) ret
=min(ret
,QueryMin(k
<<1,l
,mid
,L
,R
));if(R
>mid
) ret
=min(ret
,QueryMin(k
<<1|1,mid
+1,r
,L
,R
));return ret
;
}int FindMin(int u
)
{int ans
=INT_MAX
;while(top
[u
]!=1){ans
=min(ans
,QueryMin(1,1,n
,pos
[top
[u
]],pos
[u
]));u
=fa
[top
[u
]];}ans
=min(ans
,QueryMin(1,1,n
,1,pos
[u
]));return ans
;
}int main()
{int a
,b
,r
,l
,mid
,ans
;memset(A
,0,sizeof(A
));memset(color
,0,sizeof(color
));scanf("%d%d",&n
,&m
);for(int i
=1;i
<n
;i
++){scanf("%d%d",&a
,&b
);g
[a
].push_back(b
);g
[b
].push_back(a
);}dfs1(1,0);dfs2(1,0,1);build(1,1,n
);while(m
--){scanf("%d%d",&a
,&b
);if(a
==0) {color
[b
]=!color
[b
];update(1,1,n
,pos
[b
],color
[b
]);}else{ans
=FindMin(b
);if(ans
==INT_MAX
){printf("-1\n");}else{printf("%d\n",re
[ans
]); }}}return 0;
}
創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)
總結(jié)
以上是生活随笔為你收集整理的SPOJ - QTREE3Query on a tree again!——树链剖分的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
