Codeforces Round #264 (Div. 2) E. Caisa and Tree 树上操作暴力

http://codeforces.com/contest/463/problem/E

给出一个总节点数量为n的树，每个节点有权值，进行q次操作，每次操作有两种选项：

1. 询问节点v到root之间的路径上的各个节点，求满足条件 gcd(val[i], val[v]) > 1 的距离v最近的节点的下标。

2. 将节点v的值求改为w。

暴力居然过了！

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <string>

#include <vector>

#include <set>

#include <map>

#include <cassert>

using namespace std;

#define RD(x) scanf("%d",&x)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define clr0(x) memset(x,0,sizeof(x))

typedef long long LL;

const int maxn = 400005;

struct edge{

int next,to;

}e[maxn];

int head[maxn],n,q,w[maxn],cntn,f[maxn];

void add(int u,int v)

{

e[cntn] = (edge){head[u],v};

head[u] = cntn++;

e[cntn] = (edge){head[v],u};

head[v] = cntn++;

}

int gcd(int x,int y)

{

return y == 0 ? x:gcd(y,x%y);

}

void dfs(int u,int fa)

{

f[u] = fa;

for(int i = head[u];i != -1;i = e[i].next){

int v = e[i].to;

if(v == fa) continue;

dfs(v,u);

}

}

int find_gcd(int v)

{

int u = f[v];

while(u != -1){

int res = gcd(w[v],w[u]);

if(res > 1){

return u;

}

u = f[u];

}

return -1;

}

int main() {

RD2(n,q);

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

RD(w[i]);

int m = n - 1,u,v,ww;

memset(head,-1,sizeof(head)),clr0(f);

while(m--){

RD2(u,v);

add(u,v);

}

dfs(1,-1);

while(q--){

RD2(u,v);

if(u == 1){

printf("%d\n",find_gcd(v));

}

else{

RD(ww);

w[v] = ww;

}

}

return 0;

}

巴特西

Codeforces Round #264 (Div. 2) E. Caisa and Tree 树上操作暴力

最新文章

热门文章