首页 > 其他分享 >Codeforces1695 D1.+D2 Tree Queries

Codeforces1695 D1.+D2 Tree Queries

时间:2022-10-21 11:34:39浏览次数:62  
标签:.+ int 询问 Tree 叶子 Queries 节点 DP 条链

题意

给一个n个点的无向图,其中有一个隐藏点X,可以进行一组询问S来确定S是n个节点中的哪个点。S包括k个询问节点。询问返回的值也为k个值,每个值为X点到每个询问节点的最短路距离,求k最小为多少。

提示

1. 对于k个节点来说,最优的结构肯定是选择所有的叶子节点
2. 对于一个节点来说,假如它连了m条链(包括单个叶子节点),可以只标记m-1条链的叶子节点即可
3. 满足1,2条件以后,可以尝试再去询问点,发现均无法全部检测到,原因是:假如去点m-2条链,剩下的两条链,相同深度部分对于其他的节点来说是无法判断的,他们是等价的

方法

可以树形DP,一下,或者从每个叶子节点开始搜索一下,这里主要将树形DP的方法:
dp[i]代表除了i的子树部分外已经确定有询问点以后,子树i的内部确定所需要的询问点的最小值
只需要从度大于2的点开始DP一次就好了,因为假如度等于2的话,假如这个点连了一条直链,另一个点连了个非直链,那么必须得确保根节点选了以后才对,而两个非直链则不需要选根节点,因为显然根节点没连叶子节点,不需要选。而从度>2的点开始选,那么那么必有一个点子树内部是选了的,推出这个根节点是选了的,就满足了DP的定义(外部已经有确定的点),可以DP

代码

#include<bits/stdc++.h>

using namespace std;
vector<int> g[200004];

int dfs(int x, int fa) {
    int ans = 0, cnt = 0;
    for (auto k: g[x]) {
        if (k == fa)continue;
        int sum = dfs(k, x);
        if (sum == 0)cnt++;
        ans += sum;
    }
    return ans + max(0, cnt - 1);
}

void run() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)g[i].clear();
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].emplace_back(y);
        g[y].emplace_back(x);
    }
    if (n == 1) {
        cout << "0" << '\n';
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (g[i].size() > 2) {
            cout << dfs(i, 0) << '\n';
            return;
        }
    }
    cout << 1 << '\n';
}

int main() {
    int t;
    cin >> t;
    while (t --)
        run();
    return 0;
}

标签:.+,int,询问,Tree,叶子,Queries,节点,DP,条链
From: https://www.cnblogs.com/4VDP/p/16812896.html

相关文章

  • gin框架(1)- 路由原理:trie和radix tree
    1.前言本篇是对gin框架源码解析的第一篇,主要讲述gin的路由httprouter的原理:radixtree(压缩字典树)。2.Trie(字典树)在讲述radixtree之前,不得不简单提到radixtree......
  • Sourcetree 提交顺序
    总结:一共5个步骤1.首先获取git主分支的代码。2.暂存所需要上传的代码。3.拉取代码(如发生文件冲突先暂不处理)。4.提交代码,然后再次拉取代码(不显示冲突跳下一步)。如果......
  • B. Apple Tree 暴力 + 数学
    ​​http://codeforces.com/problemset/problem/348/B​​注意到如果顶点的数值确定了,那么它分下去的个数也就确定了,那么可以暴力枚举顶点的数值。顶点的数值是和LCM相隔的,L......
  • 史上最简单的JAVA集合(List)转树(Tree)方法
    /***将数据转换为树型结构**@paramsourcessources*@return{@linkList<DemoData>}*/publicstaticList<DemoData>transToTree(List<D......
  • Layui+treetable树实现 权限菜单多选单选
    HTML代码 所需文件我也一并上传链接:https://pan.baidu.com/s/1bAB2Pf5Dp5BDqEsMyrmWow?pwd=6666提取码:6666  效果图  需要注意的是这个不用多维数组但是要......
  • el-tree数据有部门和用户 提交只选用户
    el-tree数据有部门和用户提交只选用户数据结构其中isUser=true标识数据是用户[{"isUser":false,"id":199,"label":"陕州区",......
  • Data Structure: Tree & tree generator All In One
    DataStructure:Tree&treegeneratorAllInOne"usestrict";/****@authorxgqfrms*@licenseMIT*@copyrightxgqfrms*@created2022-10-10*@mod......
  • ClickHouse测试之mergetree中的order by字段是否符合最左原则
    先简单说一下最左原则顾名思义:1、最左优先,以最左边的为起点任何连续的索引都能匹配上。同时遇到范围查询(>,<,between,like)就会停止匹配。2、例如:b=2如果建立(a,b)顺序的索引,是......
  • CF620E New Year Tree
    题目链接题目大意\(~~\)给出一棵nn个节点的树,根节点为11。每个节点上有一种颜色c\(_{i}\)和m次操作。操作有两种:\(~~~~\)1.1\(~\)u\(~\)c:将以\(~\)u\(~\)为......
  • Codeforces Global Round 23 -D.Paths on the Tree
    题意给定一个树,树上每个节点i有一个权值s[i]。一共有k条从1(一定是根节点)开始的简单路径。设i点有c条路径通过,则其总权值为c*s.现在在限制:如果p[u]=i,p[v]=i,则abs(c[u]......