jjzjj

Codeforces1695 D1.+D2 Tree Queries

4VDP 2023-03-28 原文

题意

给一个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;
}
CodeforcesQueriesint询问font算法与数据结构

有关Codeforces1695 D1.+D2 Tree Queries的更多相关文章

  1. 李沐《动手学深度学习》d2l——安装和使用 - 2

    今天想要跟着沐神学习一下循环神经网络，在跑代码的时候，d2l出现了问题，这里记录一下解决的过程，方便以后查阅。李沐《动手学深度学习》d2l——安装和使用安装d2l解决Import“...“couldnotberesolved问题PermissionError:[WinError5]拒绝访问。:'..\\\data'安装d2l下载whl：https://www.cnpython.com/pypi/d2l/dl-d2l-0.15.1-py3-none-any.whl将下载的文件放到这里：在这个文件中右键，选择“在终端中打开”在终端中输入如下命令：condaactivatepytorch_envpi

  2. Educational Codeforces Round 146 (Rated for Div. 2)（B，E详解） - 2

    题外话：抑郁场，开局一小时只出A，死活想不来B，最后因为D题出锅ura才保住可怜的分。但咱本来就写不到DB-LongLegs（数论）本题题解法一学自同样抑郁的知乎作者幽血魅影的题解，有讲解原理。法二来着知乎巨佬cup-pyy（大佬说《不难发现》呜呜）题意三种操作：向上走mmm步向右走mmm步给自己一次走的步数加111，即使得m=m+1m=m+1m=m+1问从(0,0)(0,0)(0,0)走到(a,b)(a,b)(a,b)的最小操作次数，值得注意的是操作三不可逆。解析假设我们最终一步的大小增长到mmm，那么在这个过程中我能以[1,m][1,m][1,m]（当步数增长到该数时）之间的任何数字向上或

  3. ＆lt; nameOfproject.secondviewController的开始/结束外观过渡不平衡的调用：0x135D2A120＆gt; - 2

    我正在使用以下豆荚：https://github.com/xxxairinxxx/musicplayertransition。当我进行音乐播放器过渡并关闭它时，收集视图或表查看我在实际视图控制器上显示的内容还可以，但是当我尝试在表上做一个segue时，有一个有桌子的viewController：unbalancedcallstobegin/endappearancetransitionsfor。因此，我认为错误在吊舱上。因此，我的问题是，是否有人可以检查错误或如何防止此错误在关闭玩家后正确显示表。看答案如果是POD，您会在您搜索谷歌搜索时看到其他问题。显示您的代码，尤其是您过渡到第二控制器的位

  4. windows - ID2D1Bitmap 和 IWicBitmap 的区别 - 2

    ID2D1Bitmap和IWicBitmap有什么区别我有原始内存数据，我想创建一个位图 最佳答案 WIC位图表示系统内存中的图像，可以在widerangeofformats中(JPEG、PNG、BMP等)。D2D位图表示GPU内存中的图像，它是少数hardware-acceleratedfomats之一。.假设你想使用D2D将位图绘制到屏幕上，并且你的原始内存数据是与D2D兼容的格式，你应该使用ID2D1RenderTarget::CreateBitmap直接地。如果它不是兼容格式(例如，它是指向.png文件的原始数据的指针)，则

  5. c++ - 如何在 C++ 中将加载到内存中的图像文件转换为 ID2D1Bitmap - 2

    我正在尝试将刚刚从压缩文件提取到内存中的图像文件(png，但可以是任何文件)转换为ID2D1Bitmap，以便使用Direct2D进行绘制。我试图寻找一些文档，但我只能找到接收“constchar*路径”的方法或询问我图像的宽度和高度，我事先不知道。在谷歌上搜索它让我一无所获。该文件在内存中是原始文件，我想避免将图像提取到硬盘到一个临时文件中，只是为了从那里读取数据。有什么想法吗？ 最佳答案 如果你有HBITMAP句柄，你可以这样做:图像的大小使用:::GetObject(hBmp,sizeof(BITMAP),&bmpSizeIn

  6. javascript - 构建 tangobos 以与 DMDScript 一起工作/获取 ECMA 脚本以与 D1-Tango 一起工作 - 2

    我正在尝试安装DMDScript-tango在我的win32D1-Tango设置上。我使用的版本是0.99.9Kaibundle.当我尝试构建它时，出现以下错误(以及其他错误)C:\DMD\sources\dmdscript>dsssbuildCreatingimportsfordmdscript_tangodmdscript_tango=>dmdscript_tangodmdscript_tango\script.d(24):modulectypecannotreadfile'std\ctype.d'Commandc:\dmd\dsss\bin\rebuild.exereturned

  7. c++ - 在 D2 中读取字节的最快方法 - 2

    我想尽快从文件中读取单个字节到D2应用程序中。应用程序需要一个字节一个字节，因此读取更大的数据block不是读取器接口(interface)的选项。为此，我在C++、Java、D2中创建了一些简单的实现:https://github.com/gizmomogwai/performance.如您所见，我尝试了普通读取、应用程序代码中的缓冲区和内存映射文件。对于我的用例，内存映射解决方案效果最好，但奇怪的是D2比java慢。我希望D2介于C++和Java之间(C++代码使用-O3-g编译，D2代码使用-O-release编译)。所以请告诉我我在这里做错了什么以及如何加速D2的实现。为了让您

  8. c++ - ID2D1HwndRenderTarget 总是有黑色背景而不是透明 - 2

    我正在尝试创建一个简单的透明窗口，我可以在其中使用Direct2D进行绘图。到目前为止我做了什么:创建窗口将样式设置为WS_EX_LAYERED设置alpha颜色键为#FFF使用WindowsGraphics绘制一个白色矩形现在窗口是透明的，每像素alpha然后在窗口外制作一个目标并使用Direct2D绘制制定ALPHA_PREMULIPLIED目标使用0.0falpha清除#FFF窗口现在是黑色的我只是不知道如何使窗口透明。如果您能指出我的错误，我将不胜感激 最佳答案 这里是如何使用DirectCompositionAPI实现的俄

  9. Codeforces Round 866 (Div. 2) - 2

    A.Yura'sNewName题意：给出一个仅由_或^组成的字符串，你可以在任意位置添加_或^字符，使得字符串满足：任意字符要么属于^_^的一部分，要么属于^^的一部分。求最少添加的字符数量。分析：对于_我们只需处理没有组成^_^的_:①如果_在首位置且左边没有^则添加^②如果_在尾位置且右边没有^则添加^③如果_在中间部分且右边没有^则添加^当字符串只有一个^时末尾添加一个^code:#includeusingnamespacestd;intmain(){ std::ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); intt; cin

  10. c++ - D3D11 : How to draw GDI Text to a GXDI Surface?(无 D2D) - 2

    我需要一些帮助来使用GDI和D3D11将文本绘制到纹理。我尝试使用D2D/DirectWrite，但它只支持D3D10而不是我需要的D3D11。到目前为止我尝试的一切都失败了......现在我想使用GDI方法来写入纹理。所以我用这个参数创建了一个纹理:Usage=D3D11_USAGE_DEFAULT;Format=DXGI_FORMAT_B8G8R8A8_UNORM;BindFlags=D3D11_BIND_SHADER_RESOURCE|D3D11_BIND_RENDER_TARGET;CPUAccessFlags=0;MiscFlags=D3D11_RESOURCE_MISC_G

随机推荐