CodeforcesRound#264(Div.2)E.CaisaandTree树上操作暴力_html/css

来源：懂视网责编：小采时间：2020-11-27 15:57:03

CodeforcesRound#264(Div.2)E.CaisaandTree树上操作暴力_html/css

CodeforcesRound#264(Div.2)E.CaisaandTree树上操作暴力_html/css_WEB-ITnose:http://codeforces.com/contest/463/problem/E 给出一个总节点数量为n的树，每个节点有权值，进行q次操作，每次操作有两种选项： 1. 询问节点v到root之间的路径上的各个节点，求满足条件 gcd(val[i], val[v]) > 1 的距离v最近的节点

推荐度：

点击下载本文 文档为doc格式

导读CodeforcesRound#264(Div.2)E.CaisaandTree树上操作暴力_html/css_WEB-ITnose:http://codeforces.com/contest/463/problem/E 给出一个总节点数量为n的树，每个节点有权值，进行q次操作，每次操作有两种选项： 1. 询问节点v到root之间的路径上的各个节点，求满足条件 gcd(val[i], val[v]) > 1 的距离v最近的节点

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

给出一个总节点数量为n的树，每个节点有权值，进行q次操作，每次操作有两种选项：
1. 询问节点v到root之间的路径上的各个节点，求满足条件 gcd(val[i], val[v]) > 1 的距离v最近的节点的下标。

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

暴力居然过了！

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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;
}

声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。TEL:177 7030 7066 E-MAIL:11247931@qq.com

CodeforcesRound#264(Div.2)E.CaisaandTree树上操作暴力_html/css

推荐度：

点击下载本文 文档为doc格式

标签：操作树上 css

热门焦点

CodeforcesRound#264(Div.2)E.CaisaandTree树上操作暴力_html/css

CodeforcesRound#264(Div.2)E.CaisaandTree树上操作暴力_html/css

CodeforcesRound#264(Div.2)E.CaisaandTree树上操作暴力_html/css

最新推荐

猜你喜欢

热门推荐