D 小美的树上染色
题目描述
小美拿到了一棵树,每个节点有一个权值。初始每个节点都是白色。
小美有若干次操作,每次操作可以选择两个相邻的节点,如果它们都是白色且权值的乘积是完全平方数,小美就可以把这两个节点同时染红。
小美想知道,自己最多可以染红多少个节点?
输入描述
第一行输入一个正整数\(n\),代表节点的数量。
第二行输入\(n\)个正整数\(a_i\),代表每个节点的权值。
接下来的\(n-1\)行,每行输入两个正整数\(u,v\),代表节点\(u\)和节点\(v\)有一条边连接。
\(1\leq n \leq 10^5\)
\(1\leq a_i \leq 10^9\)
\(1\leq u,v \leq n\)
输出描述
输出一个整数,表示最多可以染红的节点数量。
解题思路
直接按照题意模拟,用dfs暴力搜索即可
代码实现
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
vector<int> g[N];
int st[N],w[N];
int ans;
void dfs(int u,int fa){
for(auto x:g[u]){
if(x==fa){
continue;
}
dfs(x,u);
if((int)sqrt(w[u]*w[x])*(int)sqrt(w[u]*w[x])==w[u]*w[x]&&(!st[x]&&!st[u])){//判断染色条件
ans+=2;
st[x]=1;
st[u]=1;
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>w[i];//权值
}
for(int i=0;i<n-1;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,-1);
cout<<ans;
return 0;
}
标签:周赛,leq,int,dfs,Round,牛客,权值,st,节点
From: https://www.cnblogs.com/udiandianis/p/18238925