AC日记——825G - Tree Queries

水深无声 2021-12-18 06:07 158阅读 0赞

[825G - Tree Queries][]

思路：

神题，路径拆成半链；

代码：

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    #define maxn 1000005
    #define INF 0x3f3f3f3f
    int n,m,val[maxn],head[maxn],E[maxn<<1],V[maxn<<1];
    int cnt,root,last,ans=INF;
    inline void in(int &now)
    {
        char Cget=getchar();now=0;
        while(Cget>'9'||Cget<'0') Cget=getchar();
        while(Cget>='0'&&Cget<='9')
        {
            now=now*10+Cget-'0';
            Cget=getchar();
        }
    }
    void dfs(int now,int fa,int Min)
    {
        val[now]=min(now,Min),Min=min(now,Min);
        for(int i=head[now];i;i=E[i])
        {
            if(fa==V[i]) continue;
            dfs(V[i],now,Min);
        }
    }
    int main()
    {
        //freopen("data.txt","r",stdin);
        in(n),in(m);int u,v;
        for(int i=1;i<n;i++)
        {
            in(u),in(v);
            E[++cnt]=head[u],V[cnt]=v,head[u]=cnt;
            E[++cnt]=head[v],V[cnt]=u,head[v]=cnt;
        }
        in(root),in(root),root=root%n+1,dfs(root,0,INF);
        for(int i=1;i<m;i++)
        {
            in(u),in(v);
            v=(last+v)%n+1;
            if(u==1) ans=min(val[v],ans);
            if(u==2) last=min(ans,val[v]),printf("%d\n",last);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/IUUUUUUUskyyy/p/7223511.html

[825G - Tree Queries]: http://codeforces.com/problemset/problem/825/G

发表评论取消回复

表情：

评论列表（有 0 条评论，158人围观）

还没有评论，来说两句吧...

相关阅读

相关 SDOI2015 寻宝游戏 | noi.ac#460 tree

题目链接：[戳我][Link 1] 可以知道，我们相当于是把有宝藏在的地方围了一个圈，求这个圈最小是多大。显然按照dfs序来遍历是最小的。那么我们就先来一遍...

╰半夏微凉°/ 2024年04月17日 05:22/ 0 赞/ 31 阅读

相关 oracle tree query

Hierarchical Queries If a table contains hierarchical data, then you can select rows in

妖狐艹你老母/ 2022年08月06日 04:06/ 0 赞/ 68 阅读

相关 CodeForces 825D(贪心)

问题描述: You are given two strings s and t consisting of small Latin letters, string s can

ゝ一纸荒年。/ 2022年06月06日 14:16/ 0 赞/ 110 阅读

相关 CodeForces 825C(贪心)

问题描述: Makes solves problems on Decoforces and lots of other different online judges. Ea

r囧r小猫/ 2022年06月06日 13:00/ 0 赞/ 111 阅读

相关 CodeForces 825B(DFS)

问题描述: Alice and Bob play 5-in-a-row game. They have a playing field of size 10 × 10. In

拼搏现实的明天。/ 2022年06月06日 12:59/ 0 赞/ 115 阅读

相关 CodeForces - 960D Full Binary Tree Queries

题目：[点击打开链接][Link 1] 题意：无限长度的二叉树,每次操作1把包含数x的那一层整体移动k个位置，正往右，负往左，操作2把包含数x的那一层带着子树移动k个位

﹏ヽ暗。殇╰゛Y/ 2022年05月08日 00:40/ 0 赞/ 92 阅读

相关 AC日记——825G - Tree Queries

[825G - Tree Queries][] 思路：　　神题，路径拆成半链；代码： include <cstdio> include <cstri

水深无声/ 2021年12月18日 06:07/ 0 赞/ 159 阅读

相关 AC日记——方格取数洛谷 P1004

题目描述设有N\N的方格图(N<=9)，我们将其中的某些方格中填入正整数，而其他的方格中则放人数字0。如下图所示（见样例）： A 0 0 0

红太狼/ 2021年12月18日 06:04/ 0 赞/ 214 阅读

相关 AC日记——最短路洛谷 P2384

题目背景狗哥做烂了最短路，突然机智的考了Bosh一道，没想到把Bosh考住了...你能帮Bosh解决吗？他会给你10000000000000000000000000

我不是女神ヾ/ 2021年12月18日 06:01/ 0 赞/ 228 阅读

相关 AC日记——Count on a tree II spoj

[Count on a tree II][] 思路：　　树上莫队；　　先分块，然后，就好办了；来，上代码： include <cmath>

╰+哭是因爲堅強的太久メ/ 2021年09月29日 04:28/ 0 赞/ 177 阅读