HDU - 6394 Tree(树分块+倍增)

http://acm.hdu.edu.cn/showproblem.php?pid=6394

题意

给出一棵树,然后每个节点有一个权值,代表这个点可以往上面跳多远,问最少需要多少次可以跳出这颗树

分析

先dfs一次得到dfs序,然后按dfs序分块。倍增计算从某点跳x到哪个点,用cn保存它跳出这一块需要的次数,ne保存跳出这块会去的点。然后块内就暴力修改了。复杂度nsqrt(n);

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(a, b) memset(a, b, sizeof(a))
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define eps 0.0000000001
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define random(a, b) rand()*rand()%(b-a+1)+a
#define pi acos(-1)
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + ;
const int maxm = + ;
const int mod = ; int w[maxn],fa[][maxn],n,m;
int head[maxn],nxt[maxn],to[maxn],tot;
int id[maxn],cnt;//dfs序
int num,block,belong[maxn],l[maxn],r[maxn];//块的数目,快的大小,属于那块,每块的左右边界
int cn[maxn],ne[maxn],pre[maxn];//跳出本块的次数,跳向的下一块的点,这个点会跳向的位置 void init(){
memset(head,-,sizeof(head));
cnt=tot=;
}
void addedge(int u,int v){
to[tot]=v;
nxt[tot]=head[u];
head[u]=tot++;
}
void dfs1(int u,int f){//dfs一次,得到dfs序和每一个点的父亲
fa[][u]=f;
id[u]=++cnt;
for(int i=head[u];~i;i=nxt[i]){
dfs1(to[i],u);
}
}
void build(){//分块
block=sqrt(n);
num=(n+block-)/block;
for(int i=;i<=n;i++){
belong[i]=(i-)/block+;
}
for(int i=;i<=num;i++){
l[i]=(i-)*block+;
r[i]=i*block;
}
r[num]=n;
}
int find(int u,int l){
for(int i=;i>=;i--){
if((l>>i)&){
u=fa[i][u];
}
}
return u;
}
void dfs2(int u){//再次dfs得到cn[N],net[N],pre[N]
int f=find(u,w[u]);
pre[id[u]]=id[f];
if(id[f]<l[belong[id[u]]]) cn[id[u]]=,ne[id[u]]=id[f];
else cn[id[u]]=cn[id[f]]+,ne[id[u]]=ne[id[f]];
for(int i=head[u];~i;i=nxt[i]){
dfs2(to[i]);
}
}
int query(int u){
int ans=;
while(u>){
ans+=cn[u];
u=ne[u];
}
return ans;
}
void update(int u,int val){
int f=find(u,val);
w[u]=val;
pre[id[u]]=id[f];
if(id[f]<l[belong[id[u]]]) cn[id[u]]=,ne[id[u]]=id[f];
else cn[id[u]]=cn[id[f]]+,ne[id[u]]=ne[id[f]];
for(int i=id[u]+;i<=r[belong[id[u]]];i++){//更新这块内后面的点
if(pre[i]>=l[belong[i]]){
cn[i]=cn[pre[i]]+;
ne[i]=ne[pre[i]];
}
}
}
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int T;
scanf("%d",&T);
while(T--){
init();
scanf("%d",&n);
for(int i=;i<=n;i++){
int x;
scanf("%d",&x);
addedge(x,i);
}
for(int i=;i<=n;i++){
scanf("%d",&w[i]);
}
dfs1(,);
for(int i=;i<;i++){
for(int j=;j<=n;j++){
fa[i][j]=fa[i-][fa[i-][j]];
}
}
build();
dfs2();
scanf("%d",&m);
while(m--){
int op,x,y;
scanf("%d%d",&op,&x);
if(op==){
printf("%d\n",query(id[x]));
}else{
scanf("%d",&y);
update(x,y);
}
}
}
return ;
}
上一篇:[转]MD5加密算法的java实现


下一篇:selenium-键盘和鼠标事件