P3258 [JLOI2014] 松鼠的新家

题目描述

松鼠的新家是一棵树，前几天刚刚装修了新家，新家有$n$ 个房间，并且有 $n-1$ 根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在“树”上。

松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去 $a_1$，再去 $a_2$，……，最后到 $a_n$，去参观新家。可是这样会导致重复走很多房间，懒惰的维尼不停地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。

维尼是个馋家伙，立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。

因为松鼠参观指南上的最后一个房间 $a_n$ 是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。

输入格式

第一行一个正整数 $n$，表示房间个数第二行 $n$ 个正整数，依次描述 $a_1,a_2,\cdots ,a_n$。

接下来 $n-1$ 行，每行两个正整数 $x,y$，表示标号 $x$ 和 $y$ 的两个房间之间有树枝相连。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

1
2
1
2
1

说明/提示

对于全部的数据，$2 \le n \le 3 \time算法思路

树结构构建：

使用邻接表存储树结构（add函数）。
节点数$n$，访问序列存储在vis数组。
预处理阶段：

DFS遍历（dfs1函数）：从根节点（设为1）出发，计算每个节点的深度$de$和直接父节点$fa[i][0]$。

倍增预处理：计算每个节点的$2^j$级祖先，用于LCA查询： $$fa[i][j]=fa[fa[i][j-1]][j-1](1\le j\le 20)$$

对数预处理：lg数组满足$2^{\text{lg}[k]-1}\le k<2^{\text{lg}[k]}$，用于LCA跳跃优化。

LCA计算（lca函数）：

调整节点深度：若$de[a]<de[b]$，交换$a,b$。
将较深节点上跳到与较浅节点同一深度：
$$a=fa[a][\text{lg}[de[a]-de[b]]-1]$$
若此时$a=b$，返回$a$；否则同步上跳至LCA的子节点： $$a=fa[a][j],b=fa[b][j](j\text{从大到小枚举})$$

最终LCA为$fa[a][0]$。

路径标记与调整：

初始化：a[vis[1]] = 1。
遍历访问序列（$i$从2到$n$）：
对相邻节点对$(vis[i-1],vis[i])$：
差分标记：b[vis[i-1]]++, b[vis[i]]++。
计算LCA（设为$js$）：b[js]–, b[fa[js][0]]–。
调整：a[vis[i-1]]–。
序列结束：a[vis[n]]–。
差分数组累加（dfs2函数）：

从叶子向根DFS，将子节点的$b$值累加到父节点： $$b[k]=b[k]+\sum _{\text{子节点}t}b[t]$$

最终答案：

对每个节点$i$，输出$a[i]+b[i]$。
复杂度分析
时间：
DFS遍历：$O(n)$
倍增预处理：$O(n\log n)$
$n-1$次LCA查询：$O(n\log n)$
差分累加：$O(n)$
总时间复杂度：$O(n\log n)$
空间：$O(n\log n)$（存储祖先数组）s 10^5$，$1\le a_i\le n$。

详细代码

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int h[N],fa[N][25];
int vis[N],lg[N],de[N];
int a[N],b[N];
int m,n,i,j,x,y,tot;
struct node{int w,to,ne;
}wc[N*2];
void add(int a,int b)
{tot++;wc[tot].w=a;wc[tot].to=b;wc[tot].ne=h[a];h[a]=tot;
}
void dfs1(int k)
{int s=h[k];while(s!=0){int t=wc[s].to;if(t!=fa[k][0]){fa[t][0]=k;de[t]=de[k]+1;dfs1(t);} s=wc[s].ne;}
}
int lca(int a,int b)
{if(de[a]<de[b]){int t=a;a=b;b=t;}while(de[a]!=de[b]){int k=lg[de[a]-de[b]]-1;a=fa[a][k];}if(a==b) return a;else{for(j=lg[de[a]]-1;j>=0;j--){if(fa[a][j]!=fa[b][j]){a=fa[a][j];b=fa[b][j];}}}return fa[a][0];
}
void dfs2(int k)
{int s=h[k];while(s!=0){int t=wc[s].to;if(t!=fa[k][0]){dfs2(t);b[k]+=b[t];}s=wc[s].ne;}
}
int main()
{ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(i=1;i<=n;i++)cin>>vis[i]; for(i=1;i<=n-1;i++){cin>>x>>y;add(x,y);add(y,x);}dfs1(1);for(j=1;j<=20;j++)for(i=1;i<=n;i++)fa[i][j]=fa[fa[i][j-1]][j-1];for(i=1;i<=n;i++)lg[i]=lg[i-1]+(1<<lg[i-1]==i?1:0);a[vis[1]]++;for(i=2;i<=n;i++){int js=lca(vis[i],vis[i-1]);b[vis[i]]++;b[vis[i-1]]++;b[js]--;b[fa[js][0]]--;a[vis[i-1]]--;}a[vis[n]]--;dfs2(1);for(i=1;i<=n;i++)cout<<a[i]+b[i]<<endl;return 0;
}