旗鼓相当的对手【Dsu on Tree】

2024-01-03 01:40
文章标签 tree 对手 dsu 旗鼓相当

本文主要是介绍旗鼓相当的对手【Dsu on Tree】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接


  有很多细节上的东西,还是需要写的细一点,不然很容易wa掉的。

  首先,以每个点作为子树的根结点来算贡献很容易发现,所以这里用一个Dsu的方法,使得O(N^2)的复杂度下降至O(N * log(N))

  然后dsu的过程一定要注意,要先算答案,再放入子树的贡献,当然算答案的时候,我们是要找对应的深度的结点。

deep[x] + deep[id] - 2 * deep[u] = K

于是我们就能算到x的深度为deep[x] = K + 2 * deep[u] - deep[id]

但是,我们必须保证deep[x] > deep[u]才能算它的贡献,因为这个等式算出来的deep[x]不保证一定是u的子结点,也有可能会额外的继承不删除的dsu部分的贡献。

deep[x] = K + 2 * deep[u] - deep[id] > deep[u]

K + deep[u] > deep[id]是不能保证的,当K比较小的时候deep[id]比较大的时候,容易出事。所以加上判断。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
//#include <unordered_map>
//#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define eps 1e-8
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1e5 + 7;
int N, K, head[maxN], cnt, a[maxN];
struct Eddge
{int nex, to;Eddge(int a=-1, int b=0):nex(a), to(b) {}
}edge[maxN << 1];
inline void addEddge(int u, int v)
{edge[cnt] = Eddge(head[u], v);head[u] = cnt++;
}
inline void _add(int u, int v) { addEddge(u, v); addEddge(v, u); }
int siz[maxN], dfn[maxN], tot, rid[maxN], Wson[maxN], deep[maxN] = {0};
void pre_dfs(int u, int fa)
{siz[u] = 1; dfn[u] = ++tot; rid[tot] = u; Wson[u] = -1;int maxx = 0;for(int i=head[u], v; ~i; i=edge[i].nex){v = edge[i].to;if(v == fa) continue;deep[v] = deep[u] + 1;pre_dfs(v, u);siz[u] += siz[v];if(maxx < siz[v]){maxx = siz[v];Wson[u] = v;}}
}
ll have_deep[maxN << 1] = {0}, num_deep[maxN << 1] = {0}, ans[maxN] = {0};
void dfs(int u, int fa, bool keep)
{for(int i=head[u], v; ~i; i=edge[i].nex){v = edge[i].to;if(v == fa || v == Wson[u]) continue;dfs(v, u, false);}if(~Wson[u]){dfs(Wson[u], u, true);}for(int i=head[u], v, id, key; ~i; i=edge[i].nex){v = edge[i].to;if(v == fa || v == Wson[u]) continue;for(int j=dfn[v]; j<dfn[v] + siz[v]; j++){id = rid[j];key = K + (deep[u] << 1) - deep[id];if(key > deep[u]) ans[u] += num_deep[key] * a[id] + have_deep[key];}for(int j=dfn[v]; j<dfn[v] + siz[v]; j++){id = rid[j];num_deep[deep[id]]++;have_deep[deep[id]] += a[id];}}num_deep[deep[u]]++;have_deep[deep[u]] += a[u];if(!keep){for(int i=dfn[u], id; i<dfn[u] + siz[u]; i++){id = rid[i];num_deep[deep[id]]--;have_deep[deep[id]] -= a[id];}}
}
inline void init()
{cnt = 0;for(int i=1; i<=N; i++) head[i] = -1;
}
int main()
{scanf("%d%d", &N, &K);init();for(int i=1; i<=N; i++) scanf("%d", &a[i]);for(int i=1, u, v; i<N; i++){scanf("%d%d", &u, &v);_add(u, v);}pre_dfs(1, 0);dfs(1, 0, true);for(int i=1; i<=N; i++) printf("%lld%c", ans[i], i == N ? '\n' : ' ');return 0;
}

 

这篇关于旗鼓相当的对手【Dsu on Tree】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/564227

相关文章

树(Tree)——《啊哈!算法》

树 什么是树?树是一种特殊的图,不包含回路的连通无向树。 正因为树有着“不包含回路”这个特点,所以树就被赋予了很多特性。 一棵树中的任意两个结点有且仅有唯一的一条路径连通。一棵树如果有n个结点,那么它一定恰好有n-1条边。在一棵树中加一条边将会构成一个回路。 一棵树有且只有一个根结点。 没有父结点的结点称为根结点(祖先)。没有子结点的结点称为叶结点。如果一个结点既不是根结点也不是叶

226 Invert Binary Tree

//226 Invert Binary Tree//算法思路:主要使用递归算法public class Solution {public TreeNode invertTree(TreeNode root) {//1 出口 空节点if (root==null)return null;//2 递归 调用自己TreeNode left = root.left;TreeNode right = ro

Sorry!Hbase的LSM Tree就是可以为所欲为!

我们先抛出一个问题: LSM树是HBase里使用的非常有创意的一种数据结构。在有代表性的关系型数据库如MySQL、SQL Server、Oracle中,数据存储与索引的基本结构就是我们耳熟能详的B树和B+树。而在一些主流的NoSQL数据库如HBase、Cassandra、LevelDB、RocksDB中,则是使用日志结构合并树(Log-structured Merge Tree,LSM Tr

【spring】does not have member field ‘com.sun.tools.javac.tree.JCTree qualid

spring-in-action-6-samples 的JDK版本 最小是11,我使用 了22: jdk21 jdk22 都与lombok 不兼容,必须使用兼容版本, 否则报错: thingsboard 的大神解释了: java: java.lang.NoSuchFieldError: Class com

【Hot100算法刷题集】哈希-01-两数之和(暴力枚举再优化,也不是哈希表的对手)

🏠关于专栏:专栏用于记录LeetCode中Hot100专题的所有题目 🎯每日努力一点点,技术变化看得见 题目转载 题目描述 🔒link->题目跳转链接 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出和为目标值 target 的那 两个整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素。 你可以按任

[LeetCode] 863. All Nodes Distance K in Binary Tree

题:https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/ 题目大意 求给树中,距给定 结点 指定长度的 所有结点的val 思路 tree -> graph 、 bfs 先遍历树,并用map记录每个结点的父结点 ,将树变为图,然后 bfs。 /*** Definition for a binary tree

js实现树级递归,通过js生成tree树形菜单(递归算法)

1、效果图 需求:首先这是一个数据集—js的类型,我们需要把生成一个tree形式的对象 : var data = [{ id: 1, name: "办公管理", pid: 0 },{ id: 2, name: "请假申请", pid: 1 },{ id: 3, name: "出差申请", pid: 1 },{ id: 4, name: "请假记录", pid: 2 },{ id:

【unity实战】利用Root Motion+Blend Tree+Input System+Cinemachine制作一个简单的角色控制器

文章目录 前言动画设置Blend Tree配置角色添加刚体和碰撞体代码控制人物移动那么我们接下来调整一下相机的视角效果参考完结 前言 Input System知识参考: 【推荐100个unity插件之18】Unity 新版输入系统Input System的使用,看这篇就够了 Cinemachine虚拟相机知识参考: 【推荐100个unity插件之10】Unity最全的最详细的C

树链剖分 + 后缀数组 - E. Misha and LCP on Tree

E. Misha and LCP on Tree  Problem's Link   Mean:  给出一棵树,每个结点上有一个字母。每个询问给出两个路径,问这两个路径的串的最长公共前缀。 analyse: 做法:树链剖分+后缀数组. 记录每条链的串,正反都需要标记,组成一个长串. 然后记录每条链对应的串在大串中的位置,对大串求后缀数组,最后询问就是在一些链

数据结构 - Codeforces Round #353 (Div. 2) D. Tree Construction

Tree Construction  Problem's Link  ---------------------------------------------------------------------------- Mean:  给定n个数,按照构造Binary Search Tree的方式来构造BST树,按顺序输出每一个非root结点的父节点的值。 analyse