codeforces 463E . Caisa and Tree

给一棵树，两种操作，一种是将点u的权值改为y，另一种是查询根节点到点u的路径上， gcd(v, u)>1的深度最深的点v。修改操作不超过50次。

这个题，暴力可以过，但是在cf上找到了一个神奇的代码。

如果没有修改，那么就将询问存起来。如果有了修改，就dfs一次，将之前的询问都处理完，然后在修改。跑的很快....

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <map>

#include <set>

#include <string>

#include <queue>

#include <stack>

#include <bitset>

using namespace std;

#define pb(x) push_back(x)

#define ll long long

#define mk(x, y) make_pair(x, y)

#define lson l, m, rt<<1

#define mem(a) memset(a, 0, sizeof(a))

#define rson m+1, r, rt<<1|1

#define mem1(a) memset(a, -1, sizeof(a))

#define mem2(a) memset(a, 0x3f, sizeof(a))

#define rep(i, n, a) for(int i = a; i<n; i++)

#define fi first

#define se second

typedef pair<int, int> pll;

const double PI = acos(-1.0);

const double eps = 1e-;

const int mod = 1e9+;

const int inf = ;

const int dir[][] = { {-, }, {, }, {, -}, {, } };

const int maxn = 1e5+;

int val[maxn], head[maxn*], num, ans[maxn];

struct node

{

    int to, nextt;

}e[maxn*];

void add(int u, int v) {

    e[num].to = v;

    e[num].nextt = head[u];

    head[u] = num++;

}

vector <int> Q[maxn], st;

void dfs(int u, int fa) {

    if(!Q[u].empty()) {

        int k = st.size()-;

        while(k>=&&__gcd(val[st[k]], val[u])==)

            k--;

        if(~k)

            k = st[k];

        for(auto i: Q[u])

            ans[i] = k;

        Q[u].clear();

    }

    st.pb(u);

    for(int i = head[u]; ~i; i = e[i].nextt) {

        int v = e[i].to;

        if(v == fa)

            continue;

        dfs(v, u);

    }

    st.pop_back();

}

int main()

{

    int n, m, x, y, sign;

    scanf("%d%d", &n, &m);

    mem1(head);

    for(int i = ; i<=n; i++)

        scanf("%d", &val[i]);

    for(int i = ; i<n-; i++) {

        scanf("%d%d", &x, &y);

        add(x, y);

        add(y, x);

    }

    int cnt = ;

    for(int i = ; i<m; i++) {

        scanf("%d", &sign);

        if(sign == ) {

            scanf("%d", &y);

            Q[y].pb(i);

            cnt++;

        } else {

            scanf("%d%d", &x, &y);

            if(cnt)

                dfs(, );

            val[x] = y;

            cnt = ;

            ans[i] = -;

        }

    }

    if(cnt)

        dfs(, );

    for(int i = ; i<m; i++) {

        if(ans[i] != -)

            printf("%d\n", ans[i]);

    }

    return ;

}

秒客网

codeforces 463E . Caisa and Tree

相关文章