2015上海网络赛 A Puzzled Elena

题意:给定一棵树，求这个节点的所有子树中包括他本身与它互质的节点的个数.

解题思路：题利用dfs序+容斥原理+前缀和性质解决。题目中要求每个结点，和多少个它的子结点互素。如果每次为了求一个点去跑一遍dfs,复杂度将是 O(N(N+M))。一定会超时。因此需要深入加以分析。注意到n的范围是10^5以内的，因此可以事先用线性筛求出每个数含有哪些素因子。接下来，我们尝试利用dfs序来求解。设num[i]表示遍历到当前结点时候，含有因数i（注意，不一定是素数）的结点个数。可以发现，如果第一次遍历到结点u，含有 u的因数的个数为a，那么第二次遍历到u时候，含有u的因数的个数变成了b，那么b-a就是u的子树中，含有u的因数的结点个数，即和u不互素的结点个数。用总的结点数减掉这部分，即得到了和u互素的结点个数。这正是用了前缀和的性质。那么，如何求解有当前有多个结点含有u的因数呢？可以利用容斥原理求解。因为我们已经预处理出来了所有数的素因数，假设有len个素因数，由于“含有”即表示只要有1个即可。因此结果就是{只含有1种素因子的个数}-{只含有2种素因子的个数}+{只含有3个素因子的个数}-...+ (-1)^(n-1){含有n个素因子的个数}。这恰好就是容斥原理。至此，问题得以解决。

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<memory.h>

 #include<cstdlib>

 #include<vector>

 #define clc(a,b) memset(a,b,sizeof(a))

 #define LL long long int

 using namespace std;

 const int N=;

 const double eps=1e-;

 const int inf=0x3f3f3f3f;

 int n;

 int val[N];

 int ans[N];

 int e;

 int num[N];

 int head[N];

 vector<int>g[N];

 struct Edge

 {

     int to,next;

 }edge[N*];

 void add(int u,int v)

 {

    edge[e].to=v;

    edge[e].next=head[u];

    head[u]=e++;

 }

 void init()

 {

     for(int i=;i<N;i++)

     {

         if(!g[i].empty())

             continue;

         for(int j=i;j<N;j+=i)

             g[j].push_back(i);

     }

 }

 int calc(int x,int y)//*y=0表示进入这颗树的时候，含有互质的数目为0；y=1表示dfs回溯的时候离开这棵树相应互质节点数目加一*//

 {

     int len=g[x].size();

     int res=;

     for(int i=;i<(<<len);i++)

     {

         int t=;

         int cnt=;

         for(int j=;j<len;j++)

         {

             if(i&(<<j))

             {

                 cnt++;

                 t=t*g[x][j];

             }

         }

         if(cnt%)

             res+=num[t];

         else

             res-=num[t];

         num[t]+=y;

     }

     return res;

 }

 int dfs(int u,int pre)

 {

     int cnt=;

     int L=calc(val[u],);

     for(int i=head[u];~i;i=edge[i].next)

     {

         int v=edge[i].to;

         if(v==pre)

             continue;

         cnt+=dfs(v,u);

     }

     int R=calc(val[u],);

     ans[u]=cnt-(R-L);

     if(val[u]==)

     ans[u]++;

     return cnt+;

 }

 int main()

 {

     int u,v;

     int cas=;

     while(~scanf("%d",&n))

     {

         e=;

         init();

         clc(num,);

         clc(head,-);

         for(int i=;i<n-;i++)

         {

             scanf("%d%d",&u,&v);

             add(u,v);

             add(v,u);

         }

         for(int i=;i<=n;i++)

         {

             scanf("%d",&val[i]);

         }

         dfs(,);

         printf("Case #%d:",cas++);

         for(int i=;i<=n;i++)

         {

            printf(" %d",ans[i]);

         }

         printf("\n");

     }

     return ;

 }

巴特西

2015上海网络赛 A Puzzled Elena

最新文章

热门文章