首页 > 其他分享 >CF911F Tree Destruction

CF911F Tree Destruction

时间:2023-05-02 15:22:05浏览次数:42  
标签:CF911F dep od Tree 结点 int edge 直径 Destruction

题意:

给你一棵 \(n\) 个结点组成的树,你需要对树进行 \(n-1\) 次操作,一次操作包含如下的步骤:

  1. 选择两个叶子结点
  2. 将这两个结点之间简单路径的长度加到答案中
  3. 从树上删去两个叶子结点之一
    初始答案为 \(0\),显然在 \(n-1\) 次操作之后树上只剩下一个结点。
    计算最大的答案,并构造一组操作序列。

思路:

构造题……向来是我不拿手的。
浅析一下本人的思考过程。一开始想的是根据结点的深度进行构造,统计出每个深度的结点个数,然后枚举最大和次大的两个深度组合出最长的路径,优先割掉个数较少的深度的点。似乎可以统计出答案,但问题在于你并不知道其中的某两个结点是不是在同一棵子树内,也就不能通过直接计算深度来求两点距离。如果加lca,时间复杂度又炸了。。。

那换一个思路,在一棵树上,且是一条距离最大的路径,似乎与树的直径有关系?
先回顾一下树的直径的一些性质:

  • 对任一一个点来说,与它距离最远的点一定是树的直径的某个端点。
  • 对于两棵树,如果第一棵树的直径的两端点为 \((x,y)\),第二棵树的直径的两端点为 \((u,v)\),那么将两棵树连起来,新树的直径的两个端点一定是四个点中的其中两个点。
  • 对于一棵树,增删一个叶子结点,最多改变直径的一个端点。
  • 如果一棵树有多条直径,那么所有直径必交于一点。
  • 任一两条直径一定有且仅有一个极长连续段重合。

对于这道题来说,第一个性质是最重要的。它为方案的构造指明了思路。

可以先两遍 \(dfs\) 找出树的一条直径,然后将所有不在直径上的点与与它距离最远的一个直径的端点配对,再把这个点删除。
对于在直径上的点,等把所有不在直径上的点全部删除后,再挨个删掉即可。

这里有个细节,当你在处理没在直径上的点,求哪个端点与与它最远时,还要记录一下这个没在直径上的点和另一个端点的lca,这样才能求距离。算是一个比较有用的技巧吧,在代码里会展示。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e5;
int n,pos[MAXN + 5][2],dp[MAXN + 5][2],tot,head[MAXN + 5],dep[MAXN + 5],S,T,ans;
bool od[MAXN + 5];//是否在直径上
vector<pair<int,int> > out;
struct EDGE{
    int u,v,next;
}edge[2 * MAXN + 5];
void add(int u,int v){
    ++tot;
    edge[tot] = (EDGE){u,v,head[u]};
    head[u] = tot;
}
void dfs(int u){//求直径
    for(int i = head[u]; i; i = edge[i].next){
        int v = edge[i].v;
        if(dep[v] < dep[u])continue;
        dep[v] = dep[u] + 1;
        dfs(v);
    }
}
void dfs1(int u){
    for(int i = head[u]; i; i = edge[i].next){
        int v = edge[i].v;
        if(dep[v] > dep[u]){
            dfs1(v);
            od[u] = od[u] || od[v];//标记是否在直径上
        }
    }
}
void dfs2(int u,int root){
	for(int i = head[u]; i; i = edge[i].next){
        int v = edge[i].v;
        if(dep[v] > dep[u])dfs2(v,(od[v] ? v : root));//如果访问到深度较当前更大的点(即父结点),假如这个点是在直径上的,那么之后从这个点出发的、不在直径上的点与直径的其中一个端点的lca就深了一层;如果不在直径上,则对lca无影响。(可以画个图想一想)
    }
    if(!od[u]){
        if(dep[u] > dep[u] + dep[T]-(dep[root]<<1)){//比较到两个端点的距离
            ans += dep[u];
            out.push_back(make_pair(S,u));
        }
        else{
            ans += dep[u] + dep[T] - (dep[root]<<1);
            out.push_back(make_pair(T,u));
        }
    }
}
signed main(){
    scanf("%lld",&n);
    for(int i = 1; i < n; i++){
        int u,v;
        scanf("%lld%lld",&u,&v);
        add(u,v);
        add(v,u);
    }
    memset(dep,0x3f,sizeof dep);
    dep[1] = 0;
    S = 1;
    dfs(S);
    for(int i = 2; i <= n; i++){
        if(dep[i] > dep[S])S = i;
    }
    memset(dep,0x3f,sizeof dep);
    dep[S] = 0;
    T = S;
    dfs(S);
    for(int i = 1; i <= n; i++){
        if(dep[i] > dep[T])T = i;
    }
    od[T] = 1;
    dfs1(S);
    dfs2(S,S);
    int now = T;
    while(now != S){
        ans += dep[now];
        for(int i = head[now]; i; i = edge[i].next){
            int v = edge[i].v;
            if(od[v] && dep[v] < dep[now]){
                out.push_back(make_pair(S,now));
                now = v;
                break;
            }
        }
    }
    cout << ans << "\n";
    for(int i = 0; i < out.size(); i++){
        cout << out[i].first << " " << out[i].second << " " << out[i].second << "\n";
    }
}

标签:CF911F,dep,od,Tree,结点,int,edge,直径,Destruction
From: https://www.cnblogs.com/CZ-9/p/17367748.html

相关文章

  • odoo tree下直接编辑, 免跳转form
      <recordid="mypartner_tree_view"model="ir.ui.view"><fieldname="name">Mypartner清单</field><fieldname="model">mypartner</field><fieldname="arch&......
  • [ABC148F] Playing Tag on Tree
    2023-03-04题目题目传送门翻译翻译难度&重要性(1~10):5题目来源AtCoder题目算法最短路解题思路考虑到T想活得久,A想尽早追上T,所以我们就将问题转化为在树上找一条最长链,使得T能比A先到达这条链。所以我们就可以在树上跑两遍单源最短路,因为边权为\(1\),所以......
  • CF 1709E XOR Tree(树上启发式合并)
    题目链接:https://codeforces.com/contest/1709/problem/E解题思路:定义sum(x,y)为x→y路径上的点的异或和,dx 为x→root路径上的点的异或和。对于一个点权树,sum(x,y)=dx ^dy ^vallca(x,y)。考虑修改一个点,可以将它改为一个很大的2为底数的幂,则经过此点的所有的不合......
  • AtCoder Regular Contest 117 D Miracle Tree
    洛谷传送门AtCoder传送门第一步就没想到可以考虑化简限制。设所有点按\(E_i\)从小到大排序后顺序是\(p_1,p_2,...,p_n\)。发现只需满足\(E_{p_{i+1}}-E_{p_i}\ge\operatorname{dis}(p_i,p_{i+1})\)。证明是对于任意\(i<j<k\),若\(p_i,p_j\)和\(p_j,p_k\)均满......
  • Codeforces 1799H - Tree Cutting(树形 dp)
    思考的时候一直卡在不会在低于\(O(n)\)的时间内储存一个连通块的\(siz\)有关的信息,看了洛谷题解之后才发现我真是个小丑。树形DP。对于一条我们需要操作的边\((i,fa_i)\),我们将其分为保留子树和删除子树两种类型,对于删除子树,我们在判定其是否合法时候改为判定删除的连通块......
  • 二叉树Binary Tree
    二叉树BinaryTree1.树的一些常用术语2.二叉树的概念树有很多种,每个节点最多只能有两个子节点的一种形式称为二叉树;二叉树的子节点分为左子节点和右子节点;以下三种均为二叉树:若该二叉树的所有叶子节点都在最后一层,且节点总数n==\(2^k\)-1,k为层数,则称为满二叉树......
  • 现在告诉你MySQL为什么选择B+Tree呢?
    大家都知道MySQL数据库选择的是B+Tree作为索引的数据结构,那为什么会选择B+Tree呢?本文分四种数据结构来分析:二叉查找树平衡二叉树多路平衡查找树加强版多路平衡查找树(B+Tree)二叉查找树二叉搜索树的特点:左子树的键值小于根的键值,右子树的键值大于根的键值。   从上面的2个图来看......
  • el-tree实现树形结构叶子节点和非叶子节点的区分显示的写法
    需求,非叶子节点显示主题名称+主题下的指标;叶子节点显示代码+名称1、设置prop属性<el-tree:data="dimListTree"ref="dimListTree"row-key="getGroup":props="treeProps":allow-drop="al......
  • 【图文详解】一文全面彻底搞懂HBase、LevelDB、RocksDB等NoSQL背后的存储原理:LSM-tree
    LSM树广泛用于数据存储,例如RocksDB、ApacheAsterixDB、Bigtable、HBase、LevelDB、ApacheAccumulo、SQLite4、Tarantool、WiredTiger、ApacheCassandra、InfluxDB和ScyllaDB等。在这篇文章中,我们将深入探讨LogStructuredMergeTree,又名LSM树:许多高度可扩展的NoSQL分......
  • Ant Design - 组件之 Tree树形控件
    AntDesign-组件之Tree树形控件针对tree树形组件封装了一个树形组件1.组件ui 2.组件名称ThemeCatalog 上面是image目录中的svg3.组件代码index.jsimportReact,{useEffect,useState}from'react';importPropTypesfrom'prop-types';importIcon,{Folde......