Codeforces 842C Ilya And The Tree

题目链接:http://codeforces.com/problemset/problem/842/C

题意:有一棵根节点为1的树,每个结点都有权值。求每个结点从根节点到它的路径上的点的最大gcd(最多把一个路径上的一个点权值变成0)。

思路:树上DFS,保存到当前节点的gcd值以及从根节点到这条路径上不选某个节点的gcd值,然后暴力更新答案就可以了。

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=200000+5;
const int INF=0x3f3f3f3f;
const int P=1000000007;
const double PI=acos(-1.0);
template<typename T> inline T gcd(T&a,T&b){return b==0?a:gcd(b,a%b);}
template<typename T> inline T lcm(T&a,T&b){return a/gcd(a,b)*b;}
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
int n,val[maxn],ans[maxn],dp[maxn];
vector<int>G[maxn],g[maxn];
void dfs(int u,int f){
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==f) continue;
        dp[v]=__gcd(dp[u],val[v]);
        g[v].push_back(dp[u]);
        for (int j=0;j<(int)g[u].size();j++){
            g[v].push_back(__gcd(g[u][j],val[v]));
        }
        sort(g[v].begin(),g[v].end());
        g[v].erase(unique(g[v].begin(),g[v].end()),g[v].end());
        dfs(v,u);
    }
}
int main(){
    read(n);
    for (int i=1;i<=n;i++) read(val[i]);
    for (int i=1;i<n;i++){
        int u,v;read(u),read(v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dp[1]=val[1],g[1].push_back(0);
    dfs(1,0);
    for (int i=1;i<=n;i++){
        if (!g[i].empty()) dp[i]=max(dp[i],g[i].back());
        printf("%d%c",dp[i],i==n?'\n':' ');
    }
    return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注