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

Rumah

hujung hadapan web

html tutorial

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

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jun 24, 2016 am 11:55 AM

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

Kenyataan Laman Web ini

Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

Menjana ai hentai secara percuma.

Tunjukkan Lagi

Artikel Panas

R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)

3 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

R.E.P.O. Tetapan grafik terbaik

3 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Assassin's Creed Shadows: Penyelesaian Riddle Seashell

2 minggu yang lalu By DDD

R.E.P.O. Cara Memperbaiki Audio Jika anda tidak dapat mendengar sesiapa

3 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

WWE 2K25: Cara Membuka Segala -galanya Di Myrise

3 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Tunjukkan Lagi

Alat panas

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Tunjukkan Lagi

Topik panas

Di manakah pintu masuk log masuk untuk e-mel gmail?

7467

Tutorial CakePHP

1376

Apakah format nama akaun stim

kunci pengaktifan win11 kekal

Sambungan NYT menunjukkan dan jawapan

Tunjukkan Lagi

Related knowledge

Apakah tujuan & lt; kemajuan & gt; unsur? Mar 21, 2025 pm 12:34 PM

Artikel ini membincangkan html & lt; kemajuan & gt; elemen, tujuan, gaya, dan perbezaan dari & lt; meter & gt; elemen. Tumpuan utama adalah menggunakan & lt; kemajuan & gt; untuk menyelesaikan tugas dan & lt; meter & gt; untuk stati

Apakah tujuan & lt; DATALIST & GT; unsur? Mar 21, 2025 pm 12:33 PM

Artikel ini membincangkan html & lt; datalist & gt; elemen, yang meningkatkan bentuk dengan menyediakan cadangan autokomplete, meningkatkan pengalaman pengguna dan mengurangkan kesilapan. Kira -kira: 159

Apakah tujuan & lt; meter & gt; unsur? Mar 21, 2025 pm 12:35 PM

Artikel ini membincangkan html & lt; meter & gt; elemen, digunakan untuk memaparkan nilai skalar atau pecahan dalam julat, dan aplikasi umum dalam pembangunan web. Ia membezakan & lt; meter & gt; dari & lt; kemajuan & gt; dan Ex

Apakah amalan terbaik untuk keserasian penyemak imbas dalam HTML5? Mar 17, 2025 pm 12:20 PM

Artikel membincangkan amalan terbaik untuk memastikan keserasian silang pelayar HTML5, memberi tumpuan kepada pengesanan ciri, peningkatan progresif, dan kaedah ujian.

Bagaimana saya menggunakan html5 & lt; masa & gt; elemen untuk mewakili tarikh dan masa secara semantik? Mar 12, 2025 pm 04:05 PM

Artikel ini menerangkan html5 & lt; time & gt; elemen untuk perwakilan tarikh/masa semantik. Ia menekankan pentingnya atribut DateTime untuk pembacaan mesin (format ISO 8601) bersama teks yang boleh dibaca manusia, meningkatkan aksesibilit

Bagaimana saya menggunakan atribut pengesahan borang html5 untuk mengesahkan input pengguna? Mar 17, 2025 pm 12:27 PM

Artikel ini membincangkan menggunakan atribut pengesahan bentuk HTML5 seperti had, corak, min, max, dan panjang untuk mengesahkan input pengguna secara langsung dalam penyemak imbas.

Apakah tag meta viewport? Mengapa penting untuk reka bentuk responsif? Mar 20, 2025 pm 05:56 PM

Artikel ini membincangkan tag Meta Viewport, penting untuk reka bentuk web responsif pada peranti mudah alih. Ia menerangkan bagaimana penggunaan yang betul memastikan skala kandungan yang optimum dan interaksi pengguna, sementara penyalahgunaan boleh membawa kepada isu reka bentuk dan kebolehaksesan.

Apakah tujuan & lt; iframe & gt; Tag? Apakah pertimbangan keselamatan semasa menggunakannya? Mar 20, 2025 pm 06:05 PM

Artikel ini membincangkan & lt; iframe & gt; Tujuan TAG dalam membenamkan kandungan luaran ke dalam halaman web, kegunaan umum, risiko keselamatan, dan alternatif seperti tag objek dan API.

See all articles