树上差分
树上差分分析
使点x到点y的路径上（链上），全加上一个值，可以选择使用树上差分（不用线段树乱搞....
首先，和普通的差分一样，要有一个tag。然而，对于一个结点，我们需要求出它全部儿子的tag之后，才能算它的tag，进而算出它的值。所以，我们需要每个节点开一个tag（不然在依次遍历儿子的时候，轻儿子的tag不就乱了嘛...会影响的嘛）（前一个括号纯属口胡，就是一个博主的sb错误）
具体操作：(cf意为差分数组)
cf[x] + 1
cf[y] + 1
cf[ lca(x,y) ] - 1 //lca(x,y)算了两遍
cf[ fa[ lca(x,y) ] ] - 1 //为了不对其它的链产生影响
裸栗题
https://www.luogu.org/problem/P3258
这题注意一下： 如果出现这样的情况：x~y, y~z， 即连续进行差分， 需要注意：cf[y]加了两次，而这题中，y是不用加两次的，所以把ans[y]--,即可 （这个操作引题而异吧，自己多想想）
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 300000+99;
const int MAXM = MAXN<<1;
int n;
struct node{
int size, deep, son, tp, fa, cf, tag;
}a[MAXN];
int visit[MAXN];
int head[MAXN], cnt;
struct seg{
int y, next;
}e[MAXM];
void add_edge(int x, int y) {
e[++cnt].y = y;
e[cnt].next = head[x];
head[x] = cnt;
}
void dfs1(int x, int fa) {
a[x].deep = a[fa].deep + 1;
a[x].fa = fa;
a[x].size = 1;
for(int i = head[x]; i; i = e[i].next)
if(e[i].y != fa) {
dfs1(e[i].y , x);
a[x].size += a[e[i].y].size ;
a[x].son = a[a[x].son].size > a[e[i].y].size ? a[x].son : e[i].y;
}
}
void dfs2(int x, int tp) {
a[x].tp = tp;
if(a[x].son) dfs2(a[x].son , tp);
for(int i = head[x]; i; i = e[i].next)
if(e[i].y != a[x].fa && e[i].y != a[x].son) {
dfs2(e[i].y, e[i].y);
}
}
int lca(int x, int y) {
while(a[x].tp != a[y].tp) {
if(a[a[x].tp].deep < a[a[y].tp].deep) swap(x, y);
x = a[a[x].tp].fa;
}
return a[x].deep < a[y].deep ? x : y;
}
void dfs3(int x) {
if(a[x].son == 0) {
a[x].tag += a[x].cf;
// printf("tag_%d : %d
",x, a[x].tag);
return ;
}
for(int i = head[x]; i; i = e[i].next)
if(e[i].y != a[x].fa) {
dfs3(e[i].y);
a[x].tag += a[e[i].y].tag ;
}
a[x].tag += a[x].cf ;//实际上还要在后面写上a[x].ans = ....
//但这题木有初值，所以我就直接用tag了
// printf("tag_%d : %d
",x, a[x].tag);
}
int main() {
scanf("%d",&n);
for(int i = 1; i <= n; i++) scanf("%d",&visit[i]);
int x,y;
for(int i = 1; i < n; i++) {
scanf("%d%d",&x, &y);
add_edge(x,y);
add_edge(y,x);
}
dfs1(1, 0);
dfs2(1, 1);
int Lca;
for(int i = 1; i < n; i++) {
a[visit[i]].cf++;
a[visit[i+1]].cf++;
Lca = lca(visit[i], visit[i+1]);
a[Lca].cf--;
a[a[Lca].fa].cf--;
}
dfs3(1);
for(int i = 2; i <= n; i++) a[visit[i]].tag--;
for(int i = 1; i <= n; i++) printf("%d
",a[i].tag);
// for(int i = 1; i <= n; i++) printf("cf_%d : %d
",i, a[i].cf);
return 0;
}
/*
5
1 4 5 3 2
1 2
2 4
2 3
4 5
*/