Codeforces Round #264 (Div. 2) E. Caisa and Tree 树上操作暴力_html/css_WEB-ITnose

php中文网

发布时间：2016-06-24 11:55:33

1056人浏览过

来源于php中文网

原创

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

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

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

暴力居然过了！

蚂蚁PPT

AI在线智能生成PPT

下载

立即学习“前端免费学习笔记（深入）”；

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

本站声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：Codeforces Round #275 (Div. 2) B Friends and Presents_html/css_WEB-ITnose 下一篇：手机Web页面如何调用手机相册跟摄像头_html/css_WEB-ITnose

热门AI工具

DeepSeek

幻方量化公司旗下的开源大模型平台

AI 编程开发 AI 聊天问答

豆包大模型

字节跳动自主研发的一系列大型语言模型

AI 编程开发 AI大模型

通义千问

阿里巴巴推出的全能AI助手

AI 编程开发 Agent智能体

腾讯元宝

腾讯混元平台推出的AI助手

文档处理 AI 聊天问答

文心一言

文心一言是百度开发的AI聊天机器人，通过对话可以生成各种形式的内容。

AI 编程开发 AI 文本写作

讯飞写作

基于讯飞星火大模型的AI写作工具，可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

AI 文本写作中文写作

即梦AI

一站式AI创作平台，免费AI图片和视频生成。

图片拼接

ChatGPT

最最强大的AI聊天机器人程序，ChatGPT不单是聊天机器人，还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

AI 编程开发 AI 文本写作

智谱清言 - 免费全能的AI助手

AI 编程开发 Agent智能体

相关专题

Golang处理数据库错误教程合集

本专题整合了Golang数据库错误处理方法、技巧、管理策略相关内容，阅读专题下面的文章了解更多详细内容。

124

2026.02.06

java多线程方法汇总

本专题整合了java多线程面试题、实现函数、执行并发相关内容，阅读专题下面的文章了解更多详细内容。

2026.02.06

1688阿里巴巴货源平台入口与批发采购指南

本专题整理了1688阿里巴巴批发进货平台的最新入口地址与在线采购指南，帮助用户快速找到官方网站入口，了解如何进行批发采购、货源选择以及厂家直销等功能，提升采购效率与平台使用体验。

674

2026.02.06

快手网页版入口与电脑端使用指南快手官方短视频观看入口

本专题汇总了快手网页版的最新入口地址和电脑版使用方法，详细提供快手官网直接访问链接、网页端操作教程，以及如何无需下载安装直接观看短视频的方式，帮助用户轻松浏览和观看快手短视频内容。

386

2026.02.06

C# 多线程与异步编程

本专题深入讲解 C# 中多线程与异步编程的核心概念与实战技巧，包括线程池管理、Task 类的使用、async/await 异步编程模式、并发控制与线程同步、死锁与竞态条件的解决方案。通过实际项目，帮助开发者掌握如何在 C# 中构建高并发、低延迟的异步系统，提升应用性能和响应速度。

2026.02.06

Python 微服务架构与 FastAPI 框架

本专题系统讲解 Python 微服务架构设计与 FastAPI 框架应用，涵盖 FastAPI 的快速开发、路由与依赖注入、数据模型验证、API 文档自动生成、OAuth2 与 JWT 身份验证、异步支持、部署与扩展等。通过实际案例，帮助学习者掌握使用 FastAPI 构建高效、可扩展的微服务应用，提高服务响应速度与系统可维护性。

2026.02.06