松鼠的新家 LCA + 树上差分

el/2024/5/23 1:29:56

题意

中文题意就不需要分析了吧

分析

首先两点之间,我们应该去走最短路径最能得到最优解,所以很容易想到求LCA,假设两点分别为x,y,LCA(x,y) = u,所以只需要把路径 x -> u -> y上的所有点加上一个糖果即可,暴力做法肯定会t,所以我们考虑一种很巧妙额做法:树上差分
两个子节点+ 1,LCA - 1最后因为LCA在这条路径上因为两点子节点都加了1,所以造成LCA增加了两次,需要给LCA和他的父节点 - 1

最后因为除了出发的点,每一个点都即成为了一次出发点,也成为了一次终点,但是只需要放置一颗糖果即可,而且最后那个点题目说了不需要放置糖果,所以需要每个点 - 1

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 3e5 + 10;
int h[N],e[N * 2],ne[N * 2],idx;
int d[N];
int a[N];
int num[N];
int ans[N];
int f[N][31];
int n,m;void add(int a,int b){ne[idx] = h[a],e[idx] = b,h[a] = idx++;
}void bfs(int root){memset(d,0x3f,sizeof d);d[0] = 0,d[root] = 1;queue<int> Q;Q.push(root);while(Q.size()){int t = Q.front();Q.pop();for(int i = h[t];~i;i = ne[i]){int j = e[i];if(d[j] > d[t] + 1){d[j] = d[t] + 1;Q.push(j);f[j][0] = t;for(int k = 1;k <= 30;k++)f[j][k] = f[f[j][k - 1]][k - 1];}}}
}int LCA(int a,int b){if(d[a] < d[b]) swap(a,b);for(int i = 30;i >= 0;i--)if(d[f[a][i]] >= d[b])a = f[a][i];if(a == b) return a;for(int i = 30;i >= 0;i--)if(f[a][i] != f[b][i])a = f[a][i],b = f[b][i];return f[a][0];
}void dfs(int u,int fa){for(int i = h[u];~i;i = ne[i]){int j = e[i];if(j == fa)continue;dfs(j, u);num[u] += num[j];}
}int main(){memset(h,-1,sizeof h);scanf("%d",&n);m = n - 1;for(int i = 1;i <= n;i++) scanf("%d",&a[i]);while(m--){int a,b;scanf("%d%d",&a,&b);add(a,b),add(b,a);}bfs(1);for(int i = 1;i < n;i++){int x = a[i],y = a[i + 1];int u = LCA(x,y);num[f[u][0]]--;num[u]--;num[x]++;num[y]++;}dfs(1,0);for(int i = 2;i <= n;i++) num[a[i]]--;for(int i = 1;i <= n;i++) printf("%d\n",num[i]);return 0;
}/**
*  ┏┓   ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃       ┃
* ┃   ━   ┃ ++ + + +
*  ████━████+
*  ◥██◤ ◥██◤ +
* ┃   ┻   ┃
* ┃       ┃ + +
* ┗━┓   ┏━┛
*   ┃   ┃ + + + +Code is far away from  
*   ┃   ┃ + bug with the animal protecting
*   ┃    ┗━━━┓ 神兽保佑,代码无bug 
*   ┃        ┣┓
*    ┃        ┏┛
*     ┗┓┓┏━┳┓┏┛ + + + +
*    ┃┫┫ ┃┫┫
*    ┗┻┛ ┗┻┛+ + + +
*/

http://www.ngui.cc/el/5239356.html

相关文章

Alyona and a tree 树上差分 +倍增

传送门 题目描述 给定一颗树&#xff0c;每个结点有对应点权&#xff0c;每条边也有对应边权。如果dis<v, u> < val[u]&#xff0c;则说明结点u被结点v所管辖。对于每个结点&#xff0c;输出它管辖的结点数目。 分析 这道题如果我们遍历每一个点并且往上爬&#x…

Snacks dfs 序 + 线段树

传送门 题目描述 百度科技园内有n个零食机&#xff0c;零食机之间通过n−1条路相互连通。每个零食机都有一个值v&#xff0c;表示为小度熊提供零食的价值。 由于零食被频繁的消耗和补充&#xff0c;零食机的价值v会时常发生变化。小度熊只能从编号为0的零食机出发&#xff0…

Count on a tree 主席树 + LCA

传送门 题目描述 给定一个包含 N 个结点的树. 树节点从 1 到 N编号.。每个节点有一个整数权值&#xff0c;查询从节点 u 到节点 v的路径上权值第k小的节点的权值。 分析 树上主席树的入门题了 我们可以用类似于树上差分的思想来处理这个问题&#xff0c;每一个节点其实就是…

Super Mario 主席树 +二分

传送门 题目描述 马里奥是一个举世闻名的管道工&#xff0c;他的跳跃能力让我们钦佩。在一条长度为n的道路上&#xff0c;在每个整数点i的位置都有一个高度为hi的障碍物。现在的问题是&#xff1a;假设马里奥可以跳跃的最高高度为H&#xff0c;在道路的[L,R] 区间内他可以跳跃…

The Door Problem 并查集

传送门 题目描述 ​有n个门和m个开关&#xff0c;每个开关可以控制任意多的门&#xff0c;每个门严格的只有两个开关控制&#xff0c;问能否通过操作某些开关使得所有门都打开。&#xff08;给出门的初始状态&#xff09;。 分析 一开始看的时候觉得是个2—sat问题&#xf…

Generate a String 线性DP + 单调队列优化

传送门 题目描述 给定正整数 n, x, y&#xff0c;你要生成一个长度为 n 的字符串&#xff0c;有两种操作&#xff1a; 添一字符或删去一个原有字符&#xff0c;代价为 x&#xff1b; 将已有字串复制粘贴一次&#xff08;翻倍&#xff09;&#xff0c;代价为 y。 求最小代价。…

Three Paths on a Tree 树的直径

传送门 题目描述 在一棵树内找三个点x,y,z&#xff0c;要求三个点之间的距离最大&#xff0c; 分析 首先我们可以找到这棵树内的直径&#xff0c;然后去去找另一点到这棵树上的直径最短 我一开始的思路是三次bfs&#xff0c;求出直径的端点&#xff0c;并且处理出每一个点…

Number of Components 思维

传送门 题目描述 分析 在一条链中&#xff0c;可以观察出结论&#xff1a;联通块数 点数 - 边数 所以我们需要求出每个点的贡献以及每一条边的贡献 首先&#xff0c;每一个点只有在 a[i] > l && a[i] < r 的时候才会被选择&#xff0c;所以每一个点的贡献应该…

To the moon 主席树 + 标记永久化

传送门 题目描述 给你一串序列&#xff0c;每次对它有四种操作&#xff0c; 1. 将l到r之间所有的数d&#xff0c;同时时间戳1。 2. 查询当前时间戳下l到r的所有数的总和。 3…查询时间戳d下的l到r的所有数的和。 4.将时间戳返回至t。 分析 主席树标记永久化的板子题了&…

CF1105E Helping Hiasat 最大独立集

传送门 题目描述 分析 最大独立集 首先相邻两个1之间的所有人最多只能选一个&#xff0c;所以我们可以把人名转换成数字&#xff0c;然后在每两个1之间的所有人之间连边 然后求补图的最大团即可 &#xff08;一开始以为是个二分图跑匈牙利&#xff0c;后来被提醒这并不是一…