コミュニティ
学ぶ
ツールライブラリ
AIツール
レジャー
検索
日本語
ホームページ ウェブフロントエンド htmlチュートリアル Codeforces Round #264 (ディビジョン 2) E. Caisa と Tree Operation での暴力_html/css_WEB-ITnose

Codeforces Round #264 (ディビジョン 2) E. Caisa と Tree Operation での暴力_html/css_WEB-ITnose

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
Jun 24, 2016 am 11:55 AM

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

ノードの合計数が n のツリーがあるとすると、各ノードには重みがあり、q 個の操作が実行され、各操作には 2 つのオプションがあります:
1. ノード v とルートの間のパス上の各ノードをクエリし、条件 gcd(val[i], val[v]) > 1 を満たす v に最も近いノードの添え字を見つけます。

2. ノード v の値を w に変更します。


暴力は実際になくなりました！

#include
#include
#include
#include
#include
#include #include
#include
#include
#include
#include
名前空間 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;
structedge{
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("%dn",find_gcd(v) );
}
else{
RD(ww);
w[v] = ww;
}
}
return 0;
}

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

もっと見る

人気の記事

R.E.P.O.説明されたエネルギー結晶と彼らが何をするか（黄色のクリスタル）
4週間前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最高のグラフィック設定
4週間前 By 尊渡假赌尊渡假赌尊渡假赌
アサシンのクリードシャドウズ：シーシェルリドルソリューション
2週間前 By DDD
R.E.P.O.誰も聞こえない場合はオーディオを修正する方法
4週間前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.チャットコマンドとそれらの使用方法
4週間前 By 尊渡假赌尊渡假赌尊渡假赌
もっと見る

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト（SublimeText3）

もっと見る

ホットトピック

Gmailメールのログイン入り口はどこですか？
7518
15
CakePHP チュートリアル
1378
52
Steamのアカウント名の形式は何ですか
80
11
Win11 Activation Key Permanent
53
19
NYTの接続はヒントと回答です
21
67
もっと見る
Related knowledge
＆lt; Progress＆gt;の目的は何ですか 要素？ ＆lt; Progress＆gt;の目的は何ですか 要素？ Mar 21, 2025 pm 12:34 PM

この記事では、HTML＆lt; Progress＆gt;について説明します。要素、その目的、スタイリング、および＆lt; meter＆gt;との違い要素。主な焦点は、＆lt; Progress＆gt;を使用することです。タスクの完了と＆lt; Meter＆gt; statiの場合

＆lt; datalist＆gt;の目的は何ですか 要素？ ＆lt; datalist＆gt;の目的は何ですか 要素？ Mar 21, 2025 pm 12:33 PM

この記事では、HTML＆lt; Datalist＆GT;について説明します。オートコンプリートの提案を提供し、ユーザーエクスペリエンスの改善、エラーの削減によりフォームを強化する要素。

HTML5のクロスブラウザー互換性のベストプラクティスは何ですか？ HTML5のクロスブラウザー互換性のベストプラクティスは何ですか？ Mar 17, 2025 pm 12:20 PM

記事では、HTML5クロスブラウザーの互換性を確保するためのベストプラクティスについて説明し、機能検出、プログレッシブエンハンスメント、およびテスト方法に焦点を当てています。

＆lt; meter＆gt;の目的は何ですか 要素？ ＆lt; meter＆gt;の目的は何ですか 要素？ Mar 21, 2025 pm 12:35 PM

この記事では、html＆lt; meter＆gt;について説明します。要素は、範囲内でスカラーまたは分数値を表示するために使用され、Web開発におけるその一般的なアプリケーション。それは差別化＆lt; Meter＆gt; ＆lt; Progress＆gt;およびex

HTML5フォーム検証属性を使用してユーザー入力を検証するにはどうすればよいですか？ HTML5フォーム検証属性を使用してユーザー入力を検証するにはどうすればよいですか？ Mar 17, 2025 pm 12:27 PM

この記事では、ブラウザのユーザー入力を直接検証するために、必要、パターン、MIN、MAX、および長さの制限などのHTML5フォーム検証属性を使用して説明します。

ビューポートメタタグとは何ですか？レスポンシブデザインにとってなぜそれが重要なのですか？ ビューポートメタタグとは何ですか？レスポンシブデザインにとってなぜそれが重要なのですか？ Mar 20, 2025 pm 05:56 PM

この記事では、モバイルデバイスのレスポンシブWebデザインに不可欠なViewportメタタグについて説明します。適切な使用により、最適なコンテンツのスケーリングとユーザーの相互作用が保証され、誤用が設計とアクセシビリティの問題につながる可能性があることを説明しています。

＆lt; iframe＆gt;の目的は何ですか タグ？使用する際のセキュリティ上の考慮事項は何ですか？ ＆lt; iframe＆gt;の目的は何ですか タグ？使用する際のセキュリティ上の考慮事項は何ですか？ Mar 20, 2025 pm 06:05 PM

この記事では、＆lt; iframe＆gt;外部コンテンツをWebページ、その一般的な用途、セキュリティリスク、およびオブジェクトタグやAPIなどの代替案に埋め込む際のタグの目的。

Giteeページ静的なWebサイトの展開に失敗しました：単一のファイル404エラーをトラブルシューティングと解決する方法 Giteeページ静的なWebサイトの展開に失敗しました：単一のファイル404エラーをトラブルシューティングと解決する方法 Apr 04, 2025 pm 11:54 PM

GiteEpages静的Webサイトの展開が失敗しました：404エラーのトラブルシューティングと解像度Giteeを使用する

See all articles