【1】中我们学习了树上差分，并且a了一个裸的点差分. 现在继续树上差分~ 洛谷 P3258 [JLOI2014]松鼠的新家
分析题目描述
松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，
且俩个房间之间的路线都是唯一的。天哪，他居然真的住在”树“上。
松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a1，再去
a2，......，最后到an，去参观新家。可是这样会导致维尼重复走很多房间，懒惰的维尼不停地推辞。可是松鼠告
诉他，每走到一个房间，他就可以从房间拿一块糖果吃。
维尼是个馋家伙，立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。
因为松鼠参观指南上的最后一个房间an是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。
输入格式
第一行一个整数n，表示房间个数第二行n个整数，依次描述a1-an
接下来n-1行，每行两个整数x，y，表示标号x和y的两个房间之间有树枝相连。
输出格式
一共n行，第i行输出标号为i的房间至少需要放多少个糖果，才能让维尼有糖果吃。
输入输出样例
输入 #1复制
5
1 4 5 3 2
1 2
2 4
2 3
4 5
输出 #1复制
1
2
1
2
1
说明/提示
2<= n <=300000
裸的点差分.
显然，小熊维尼的路线是 a1—a2、a2—a3、…a_{n-1}–an, 这些都是树上路径. 树上路径会造成一些树上节点的覆盖. 只需差分完毕之后dfs一波即可~ 但是注意，an这个点不需要放置糖果的意思是最后到达an的时候不需要吃糖果了，但是中途其他边可能路过an, 还是要放糖果的~ 所以最后 b[an]-- 即可. 但是从ai（i>1）到a\_{i+1} a[i]是不需要再放糖果的. 所以只要i不等于a[1]（特别的, an 就不等于a[1]）, 最后dfs完了之后就要自减1, 只是an和其他a[2,…,n-1]自减的原因不一样, an是因为最后不需要准备糖果，而a[i= 2,…,n-1]自减1是因为从ai出发不再需要放糖果.
//#include "stdafx.h"
#include
#include
#include
using namespace std;
//#define LOCAL
const int maxn = 3e5+5, maxl = 21;
int n, a[maxn], cnt, head[maxn], fa[maxn][maxl], dep[maxn], b[maxn];
bool v[maxn];
struct Arc
{
int from, to, nxt;
}g[maxn < dep[y])
{
swap(x, y);
}
for (int j = maxl - 1; ~j; j--)
{
if (dep[fa[y][j]] >= dep[x])
{
y = fa[y][j];
}
}
if (x == y)
{
return x;
}
for (int j = maxl - 1; ~j; j--)
{
if (fa[x][j] ^ fa[y][j])
{
x = fa[x][j];
y = fa[y][j];
}
}
return fa[x][0];
}
void cf(int x, int y)
{
int a = lca(x, y);
++b[x];
++b[y];
--b[a];
--b[fa[a][0]];
}
void dfs1(int cur)
{
v[cur] = true;
for (int h = head[cur], to; ~h; h = g[h].nxt)
{
to = g[h].to;
if (v[to])
{
continue;
}
dfs1(to);
b[cur] += b[to];
}
}
int main()
{
#ifdef LOCAL
freopen("d:\\data.in","r",stdin);
// freopen("d:\\my.out", "w", stdout);
#endif
memset(head, -1, sizeof(head));
scanf("%d", &n);
for (int i = 1; i<=n; i++)
{
scanf("%d", a + i);
}
int x, y;
for (int i = 1;i < n; i++)
{
scanf("%d%d", &x, &y);
addarc(x, y);
addarc(y, x);
}
dep[1] = 1;
dfs(1);
for (int j = 1, pa; j < maxl; j++)
{
for (int i = 1; i <= n; i++)
{
pa = fa[i][j - 1];
fa[i][j] = fa[pa][j - 1];
}
}
for (int i = 1; i < n; i++)
{
x = a[i];
y = a[i + 1];
cf(x, y);
}
memset(v, 0, sizeof(v));
dfs1(1);
for (int i = 1; i <= n; i++)
{
if (i ^ a[1])
{
--b[i];
}
printf("%d\n", b[i]);
}
return 0;
}
ac情况
所属题目
P3258 [JLOI2014]松鼠的新家
评测状态
Accepted
评测分数
100
编程语言
C++
代码长度
1.96KB
用时
934ms
内存
43.81MB
参考
【1】https://blog.csdn.net/anfengliuzhiwu/article/details/104434740