1.題目描述：點擊打開鏈接

2.解題思路：本題利用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個素因子的個數}。這恰好就是容斥原理。至此，問題得以解決。

3.代碼：

#include<iostream> #include<algorithm> #include<cassert> #include<string> #include<sstream> #include<set> #include<bitset> #include<vector> #include<stack> #include<map> #include<queue> #include<deque> #include<cstdlib> #include<cstdio> #include<cstring> #include<cmath> #include<ctime> #include<cctype> #include<list> #include<complex> #include<functional> using namespace std;#define me(s) memset(s,0,sizeof(s)) #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; typedef pair <int,int> P;const int N = 100000 + 10; vector<int>g[N]; int num[N]; int val[N]; int L[N], R[N], ans[N]; struct Edge {int to, next; }edge[N << 2]; int head[N]; int e, n;void init() {for (int i = 2; i<N; i++){if (!g[i].empty())continue;for (int j = i; j<N; j += i)g[j].pb(i);} }void addedge(int u, int v) {edge[e].to = v;edge[e].next = head[u];head[u] = e++; }int bitcount(int x) { return !x ? 0 : bitcount(x / 2) + (x & 1); }int calc(int x, int val)//計算當前有多少個結點含有x的因數，val=0表示不更新num數組，val=1表示用x來更新num數組 {int len = g[x].size();int res = 0;for (int i = 1; i<1 << len; i++){int t = 1;for (int j = 0; j<len; j++)if (i >> j & 1)t *= g[x][j];if (bitcount(i) & 1)res += num[t];else res -= num[t];num[t] += val;}return res; }int dfs(int u, int fa)//dfs返回的是u這棵子樹的總結點數 {int cnt = 0;L[u] = calc(val[u], 0);for (int i = head[u]; ~i; i = edge[i].next){int v = edge[i].to;if (v != fa)cnt += dfs(v, u);}R[u] = calc(val[u], 1);ans[u] = cnt - (R[u] - L[u]);if (val[u] == 1)ans[u]++; //注意！1和自身也互素return cnt + 1; }int main() {init();int n;int kase = 0;while (~scanf("%d", &n)){e = 0;memset(head, -1, sizeof(head));me(num);int u, v;for (int i = 1; i<n; i++){scanf("%d%d", &u, &v);u--, v--;addedge(u, v);addedge(v, u);}for (int i = 0; i<n; i++)scanf("%d", &val[i]);dfs(0, -1);printf("Case #%d:", ++kase);for (int i = 0; i<n; i++)printf(" %d", ans[i]);puts("");} }

總結

以上是生活随笔為你收集整理的HDU 5468 Puzzled Elena （2015年上海赛区网络赛A题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。