code

用户名：wjh31415926535

访问量：972

签　名：

等　　级
排　　名	26280
经　　验	579
参赛次数	1
文章发表	4
年　　龄	0
在职情况	学生
学　　校	华南农业大学
专　　业

　　自我简介：

TA的其他文章

前驱后驱数组 + 优先队列
浏览：359

tarjan算法求lca
浏览：251

tarjan + lca + 树上差分
浏览：299

你可能喜欢

tarjan + lca + 树上差分

　　作者: code　　　　发表时间：2023-04-19 18:26:28 浏览：299　|　评论：0　

原题链接：蓝桥杯2023年第十四届省赛真题-砍树

# 思路
* 主要讲讲怎么在边上树上差分吧
	 具体的思路就是，将要查询`diff[u] +=1,diff[v] += 1, diff[lca]-=2`,然后
* 状态一
![](/image_editor_upload/20230419/20230419062353_26098.png)
* 状态二
![](/image_editor_upload/20230419/20230419062440_27037.png)
我们在递归的过程中，就查看当前点`u`它的子节点`v`，是否等于m，如果等于m说明u节点和v节点之间的边可以被删除。
于是我们就可以得到下面的代码啦
```cpp
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <string>
#include<functional>
#include <math.h>
#include <algorithm>
#include<unordered_map>
#include<ctime>
#include <cstring>
#define lowbit(x) (-x) & x
#define ll long long
const int N = 3e6;
using namespace std;    
const int mod = 1e9 + 7;
ll __pow(ll x,ll y){
	ll res = 1;
	while(y){
		if(y&1)res = (res * x);
		y>>=1;
		x = (x * x);
	}
	return res;
}
ll cal(ll v1, ll v2){
	return v1*__pow(v2,mod-2)%mod;
}
ll C(ll x,ll y){
    ll res = 1;
    for(int i = 1,j = x + 1; j <= y;j++, i++){
        res*=j;
        res/=i;
    }
    return res;
}
ll gcd(ll x, ll y){
    if(y == 0)return x;
    else return gcd(y, x%y);
}
struct node{
    int to,nxt,c = 0,idx;
}e[N];
int cnt = 0;
int head[N];
void add(int u, int v){
    e[++cnt].nxt = head[u];
    e[cnt].to = v;
    head[u] = cnt;
    e[cnt].c = 0;
    e[cnt].idx = (cnt + 1)/2;
}
void solve(){   
    int n,m;
    cin>>n>>m;
    for(int i = 0; i < n - 1; ++i){
        int u,v;
        cin>>u>>v;
        u--,v--;
        add(u, v);
        add(v, u);
    }
    map<ll,int>lca;
    vector<int>query[n];
    for(int i = 0; i < m;++i){
        int u, v;
        cin>>u>>v;
        u--, v--;
        query[u].push_back(v);
        query[v].push_back(u);
    } 
    int p[n];
    int f[n];
    vector<int>diff(n, 0);
    vector<int>color(n, 0);
    for(int i = 0; i < n;++i)f[i] = i;
    function<int(int)>find = [&](int x)->int{return (f[x] == x)?x : f[x] = find(f[x]);};
    function<void(int,int)>tarjan = [&](int u,int fa){
        color[u] = 1;
        p[u] = fa;
        for(int i = head[u];i ; i = e[i].nxt){
            int v = e[i].to;
            if(color[v]==0){
                tarjan(v, u);
                f[v] = u;
            }
        }
        for(int v : query[u]){
            if(color[v]==2 || u == v){
                int ffa = find(v);
                diff[u]++;
                diff[v]++;
                lca[(ll)u*(1ll<<32) + v] = ffa;
                lca[(ll)v*(1ll<<32) + u] = ffa;
                diff[ffa]-=2;
            }
        }
        color[u] = 2;
    };
    tarjan(0, -1);
    int maxe = -1;
    function<void(int,int)>dfs = [&](int u, int fa){
        for(int i = head[u];i; i = e[i].nxt){
            int v = e[i].to;
            if(v == fa)continue;
            dfs(v, u);
            int id = e[i].idx;
            diff[u] += diff[v];    
            if(diff[v] == m){
                maxe = max(maxe, id);
            }
        }   
    };
    dfs(0, -1);
    cout<<maxe<<endl;
}   
int main(){ 
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    int t;
    t = 1;
    while(t--){
        solve();
    }
    return 0 ;
}   
```

0.0分

4 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

code

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

【蟠桃记】（C语言代码）

C二级辅导-求偶数和（C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

tarjan + lca + 树上差分

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.4 （Java代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

人见人爱A+B （C语言代码）

最小公倍数（C语言代码）

【亲和数】（C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

校门外的树（C语言代码）

求圆的面积（C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

code

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

【蟠桃记】 （C语言代码）

C二级辅导-求偶数和 （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

tarjan + lca + 树上差分

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.4 （Java代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

人见人爱A+B （C语言代码）

最小公倍数 （C语言代码）

【亲和数】 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

校门外的树 （C语言代码）

求圆的面积 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

【蟠桃记】（C语言代码）

C二级辅导-求偶数和（C语言代码）

　　评论区

最小公倍数（C语言代码）

【亲和数】（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

校门外的树（C语言代码）

求圆的面积（C语言代码）