AC日记——825G - Tree Queries

水深无声 2021-12-18 06:07 202阅读 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 条评论，202人围观）

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

相关阅读

相关 Codeforces Round #582 (Div. 3) G. Path Queries

Codeforces Round \582 (Div. 3) G. Path Queries [题目描述][Link 1] 个人感觉这道题目的思路比较像最小瓶颈生成树，

刺骨的言语ヽ痛彻心扉/ 2023年06月01日 15:54/ 0 赞/ 2 阅读

相关 oracle tree query

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

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

相关 CodeForces 825D(贪心)

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

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

相关 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 赞/ 151 阅读

相关 CodeForces 825A(脑洞)

问题描述: Polycarp has just invented a new binary protocol for data transmission. He is enc

Bertha 。/ 2022年06月06日 12:38/ 0 赞/ 179 阅读

相关 CF1110G Tree-Tac-Toe（博弈论）

题面 [传送门][Link 1] 题解博弈论的前提是双方都是绝顶聪明的人所以这种题目显然不是我应该做的 [题解][Link 2] //minam

一时失言乱红尘/ 2021年12月23日 05:43/ 0 赞/ 255 阅读

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

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

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

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

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

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

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

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

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

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

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

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