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

最新推薦

猜你喜歡

熱門推薦