Tree difference

The difference in the tree

General introduction

  The difference on the tree is almost the same as the ordinary interval difference , It solves the problem of modifying the last query offline for many times （ Don't tell me you can't do array differencing qwq）.

  Pre cheese ： Multiply the demand $LCA$、 Normal difference

Point difference

  For example, such a question , Every time you modify a path in the tree , The point weights of all points on this path are added $k$, Finally, query the point weight of a point .

  Consider emulating the difference approach of ordinary arrays , Maintain the differential array for the nodes on the tree $c$, We consider a path （ The starting point and the ending point are $s,t$） The weight of all points on the plus $k$, So the difference array should change like this ：

$$\begin{array}{rl}c[s]+=k,& c[t]+=k\\ c[lca(s,t)]-=k,c[& f[lca(s,t)][0]]-=k\end{array}$$

  above $lca(s,t)$ Express $s$ and $t$ The latest public ancestor of , $f$ An array is a multiplication $lca$ Used in $f$, $f[lca(s,t)][0]$ It means the father of the nearest public ancestor .

  This operation should not be difficult to understand , As long as the formula is listed, it should be I can understand .

  At the last inquiry , We only need to make a subtree sum to get the weight of each point （ Namely $dfs$ Just one more time ）.

  Find a problem to practice ：luogu3258 Squirrel's new home

#include<bits/stdc++.h>
using namespace std;
#define in read()
#define MAXN 300300
#define MAXM 4 * MAXN

inline int read(){
    
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <=c and c <= '9'){
    
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int n = 0;
int a[MAXN] = {
     0 };

int tot = 0;
int first[MAXN] = {
     0 };
int   nxt[MAXM] = {
     0 };
int    to[MAXM] = {
     0 };
int     c[MAXN] = {
     0 };
int   ans[MAXN] = {
     0 };

inline void add(int x, int y){
    
	nxt[++tot] = first[x];
	first[x] = tot; to[tot] = y;
}

int dep[MAXN] = {
     0 };
int f[MAXN][35] = {
     0 };
void prework(int x, int fa){
    
	dep[x] = dep[fa] + 1;
	for(int i = 0; i <= 30; i++) f[x][i + 1] = f[f[x][i]][i];
	for(int e = first[x]; e; e = nxt[e]){
    
		int y = to[e];
		if(y == fa) continue;
		f[y][0] = x;
		prework(y, x);
	}
}

int LCA(int x, int y){
    
	if(dep[x] < dep[y]) swap(x, y);
	for(int i = 30; i >= 0; i--){
    
		if(dep[f[x][i]] >= dep[y]) x = f[x][i];
		if(x == y) return x;
	}
	for(int i = 30; i >= 0; i--)
		if(f[x][i] != f[y][i])
			x = f[x][i], y = f[y][i];
	return f[x][0];
}

void dfs(int x, int fa){
    
	for(int e = first[x]; e; e = nxt[e]){
    
		int y = to[e];
		if(y == fa) continue;
		dfs(y, x);
		c[x] += c[y];
	}
}

int main(){
    
	n = in;
	for(int i = 1; i <= n; i++) a[i] = in;
	for(int i = 1; i < n; i++){
    
		int x = in, y = in;
		add(x, y); add(y, x);
	}
	prework(1, 0);
	for(int i = 1; i < n; i++){
    
		int x = a[i], y = a[i + 1];
		int lca = LCA(x, y);
		c[x]++, c[y]++, c[lca]--, c[f[lca][0]]--;
	}
	dfs(1, 0); c[a[1]]++;
	for(int i = 1; i <= n; i++) cout << c[i] - 1 << '\n';
	return 0;
}

Edge difference

  Consider such a question , One path for each change , All edges on this path are weighted plus $1$. Finally, query the edge weight .

  Record two arrays $sum$ and $prev$.$su{m}_x$ Indication point $x$ To $fa(x)$ The number of occurrences of this side of . $prev$ Record each point to its father's side .

  Give a path for each operation （ The starting point and the ending point are $s,t$）, That's how we deal with it ：

$$\begin{array}{rl}sum[s& ]++,sum[t]++\\ sum& [lca(s,t)]-=2\end{array}$$

  Then we finished .

  Find another exercise to practice ：NOIP2015 transport plan

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in read()
#define MAXN 300300
#define MAXM 4 * MAXN
#define INFI (int)3e8

inline int read(){
    
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
    
		x = x * 10 + c - '0'; c=  getchar();
	}
	return x;
}

int tot = 0;
int first[MAXN] = {
     0 };
int   nxt[MAXM] = {
     0 };
int    to[MAXM] = {
     0 };
int value[MAXM] = {
     0 };
inline void add(int x, int y, int weight){
    
	nxt[++tot] = first[x];
	first[x] = tot; to[tot] = y;
	value[tot] = weight;
}

int pre[MAXN] = {
     0 };
int dis[MAXN] = {
     0 };
int dep[MAXN] = {
     0 };
int f[MAXN][32] = {
     0 };
void prework(int x, int fa){
    
	dep[x] = dep[fa] + 1;
	for(int i = 0; i <= 30; i++) f[x][i + 1] = f[f[x][i]][i];
	for(int e = first[x]; e; e = nxt[e]){
    
		int y = to[e];
		if(y == fa) continue;
		f[y][0] = x; dis[y] = dis[x] + value[e]; pre[y] = value[e];
		prework(y, x);
	}
}

int LCA(int x, int y){
    
	if(dep[x] < dep[y]) swap(x, y);
	for(int i = 30; i >= 0; i--){
    
		if(dep[f[x][i]] >= dep[y]) x = f[x][i];
		if(x == y) return x;
	}
	for(int i = 30; i >= 0; i--)
		if(f[x][i] != f[y][i])
			x = f[x][i], y = f[y][i];
	return f[x][0];
}

int n = 0; int m = 0;
struct Tedge{
    
	int len;
	int x, y, lca;
	bool operator < (const Tedge &rhs) const {
     return len > rhs.len; }
}edge[MAXM];

int mx = 0; int cnt = 0;
int flag = 0;
int sum[MAXN] = {
     0 };

int judge(int x, int fa, int cnt, int mx){
    
	int num = sum[x];
	for(int e = first[x]; e; e = nxt[e]){
    
		int y = to[e];
		if(y == fa) continue;
		num += judge(y, x, cnt, mx);
	}
	if(num >= cnt and pre[x] >= mx) flag = 1;
	return num;
}

int check(int x){
    
	cnt = mx = flag = 0; memset(sum, 0, sizeof(sum));
	for(int i = 1; i <= m; i++){
    
		if(edge[i].len > x){
    
			sum[edge[i].x]++, sum[edge[i].y]++, sum[edge[i].lca] -= 2;
			cnt++; mx = max(mx, edge[i].len);
		}
	}
	if(cnt == 0) return 1;
	int k = judge(1, 0, cnt, mx - x);
	return flag;
}

signed main(){
    
	n = in; m = in;
	for(int i = 1; i < n; i++){
    
		int x = in, y = in, w = in;
		add(x, y, w); add(y, x, w);
	} prework(1, 0);
// for(int i = 1; i <= n; i++) cout << dis[i] << ' '; puts("");
// for(int i = 1; i <= n; i++) cout << pre[i] << ' '; puts("");
	for(int i = 1; i <= m; i++){
    
		edge[i].x = in; edge[i].y = in;
		edge[i].lca = LCA(edge[i].x, edge[i].y);
		edge[i].len = dis[edge[i].x] + dis[edge[i].y] - 2 * dis[edge[i].lca];
	}
	int l = 0; int r = INFI;
	while(l < r){
    
		int mid = (l + r) >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << l << '\n';
	return 0;
}