BZOJ 3631: [JLOI2014]松鼠的新家( 树链剖分 )

BZOJ 3631: [JLOI2014]松鼠的新家( 树链剖分 )

裸树链剖分...

-------------------------------------------------------------------

#include<bits/stdc++.h>
 
using namespace std;
 
const int maxn = 300009;
 
struct edge {
int to;
edge* next;
} E[maxn << 1], *pit = E, *head[maxn];
 
inline void add(int u, int v) {
pit->to = v;
pit->next = head[u];
head[u] = pit++;
}
#define addedge(u, v) add(u, v), add(v, u)
#define M(l, r) (((l) + (r)) >> 1)
 
int dep[maxn], size[maxn], son[maxn], fa[maxn], top[maxn], id[maxn], TOP, CK = 0;
 
void dfs(int x) {
son[x] = -(size[x] = 1);
for(edge* e = head[x]; e; e = e->next) if(e->to != fa[x]) {
dep[e->to] = dep[x] + 1;
fa[e->to] = x;
dfs(e->to);
size[x] += size[e->to];
if(!~son[x] || size[son[x]] < size[e->to])
   son[x] = e->to;
}
}
 
void DFS(int x) {
top[x] = TOP;
id[x] = ++CK;
if(~son[x]) DFS(son[x]);
for(edge* e = head[x]; e; e = e->next) 
   if(e->to != son[x] && e->to != fa[x]) DFS(TOP = e->to);
}
 
void init() {
dfs(dep[0] = 0);
DFS(TOP = 0);
}
 
struct Node {
Node *l, *r;
int add;
Node():add(0) {}
} pool[maxn * 20], *pt = pool, *root;
 
void build(Node* t, int l, int r) {
if(r > l) {
int m = M(l, r);
build(t->l = pt++, l, m);
build(t->r = pt++, m + 1, r);
}
}
 
int L, R, N;
 
void modify(Node* t, int l, int r) {
if(L <= l && r <= R)
   t->add++;
else {
int m = M(l, r);
if(L <= m) modify(t->l, l, m);
if(m < R) modify(t->r, m + 1, r);
}
}
 
int query(Node* t, int l, int r) {
R += t->add;
if(l == r)
   return R;
int m = M(l, r);
return L <= m ? query(t->l, l, m) : query(t->r, m + 1, r);
}
 
void change(int x, int y) {
for(; top[x] != top[y]; x = fa[top[x]]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
L = id[top[x]]; R = id[x];
modify(root, 1, N);
}
if(dep[x] < dep[y]) swap(x, y);
L = id[y]; R = id[x];
modify(root, 1, N);
}
 
int path[maxn];
 
int main() {
cin >> N;
for(int i = 0; i < N; i++)
   scanf("%d", path + i), path[i]--;
for(int i = 0; i < N - 1; i++) {
int u, v; scanf("%d%d", &u, &v); --u; --v;
addedge(u, v);
}
init();
build(root = pt++, 1, N);
for(int i = 1; i < N; i++)
   change(path[i - 1], path[i]);
for(int i = 0; i < N; i++) {
L = id[i]; R = 0;
int t = query(root, 1, N);
if(i != path[0]) t--;
printf("%d\n", t);
}
return 0;
}

-------------------------------------------------------------------

3631: [JLOI2014]松鼠的新家

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 855  Solved: 412
[Submit][Status][Discuss]

Description

松鼠的新家是一棵树,前几天刚刚装修了新家,新家有n个房间,并且有n-1根树枝连接,每个房间都可以相互到达,且俩个房间之间的路线都是唯一的。天哪,他居然真的住在“树”上。松鼠想邀请小熊维尼前来参观,并且还指定一份参观指南,他希望维尼能够按照他的指南顺序,先去a1,再去a2,……,最后到an,去参观新家。
可是这样会导致维尼重复走很多房间,懒惰的维尼不听地推辞。可是松鼠告诉他,每走到一个房间,他就可以从房间拿一块糖果吃。维尼是个馋家伙,立马就答应了。
现在松鼠希望知道为了保证维尼有糖果吃,他需要在每一个房间各放至少多少个糖果。因为松鼠参观指南上的最后一个房间an是餐厅,餐厅里他准备了丰盛的大餐,所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。

Input

第一行一个整数n,表示房间个数
第二行n个整数,依次描述a1-an
接下来n-1行,每行两个整数x,y,表示标号x和y的两个房间之间有树枝相连。

Output

一共n行,第i行输出标号为i的房间至少需要放多少个糖果,才能让维尼有糖果吃。

Sample Input

5
1 4 5 3 2
1 2
2 4
2 3
4 5

Sample Output

1
2
1
2
1

HINT

2<= n <=300000

Source

上一篇:ES6、7、8常用新特性总结(超实用)


下一篇:HTML5,CSS3新特性,与旧版的区别