コミュニティ
学ぶ
ツールライブラリ
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

WBOY
リリース： 2016-06-24 11:55:33
オリジナル
942 人が閲覧しました

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

関連ラベル：
Codeforces Round #264 (Div. 2) E. Caisa and Tree 树上操作暴力
ソース：php.cn
前の記事：Codeforces ラウンド #275 (ディビジョン 2) B 友人とプレゼント_html/css_WEB-ITnose 次の記事：モバイル Web ページ 携帯電話のアルバムとカメラの呼び出し方法_html/css_WEB-ITnose
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
著者別の最新記事
最新の問題
function_exists() はカスタム関数を決定できません Function test () {return true;} if (function_exists ('test')) {echo "テストは関数です";
から 2024-04-29 11:01:01
0
3
2497
Google Chromeのモバイル版を表示する方法 こんにちは、先生、Google Chrome をモバイル版に変更するにはどうすればよいですか?
から 2024-04-23 00:22:19
0
11
2643
子ウィンドウは親ウィンドウを操作しますが、出力は応答しません。 最初の 2 つの文は実行可能ですが、最後の文は実装できません。
から 2024-04-19 15:37:47
0
1
2232
親ウィンドウには出力がありません document.onclick = function(){ window.opener.document.write('私は子ウィンドウの出力です');
から 2024-04-18 23:52:34
0
1
2097
CSS マインド マッピングに関するコースウェアはどこにありますか? コースウェア
から 2024-04-16 10:10:18
0
0
2200
関連トピック
詳細>
人気のおすすめ
人気のチュートリアル
詳細>
関連するチュートリアル
人気のおすすめ
最新のコース
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート