HDU 5468 Puzzled Elena(DFS序+モビウス反転好題)
Puzzled Elena
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 470 Accepted Submission(s): 103
Problem Description
Since both Stefan and Damon fell in love with Elena, and it was really difficult for her to choose. Bonnie, her best friend, suggested her to throw a question to them, and she would choose the one who can solve it. Suppose there is a tree with n vertices and n - 1 edges, and there is a value at each vertex. The root is vertex 1. Then for each vertex, could you tell me how many vertices of its subtree can be said to be co-prime with itself? NOTES: Two vertices are said to be co-prime if their values' GCD (greatest common divisor) equals 1.
Input
There are multiply tests (no more than 8). For each test, the first line has a number n (1≤n≤105) , after that has n−1 lines, each line has two numbers a and b (1≤a,b≤n) , representing that vertex a is connect with vertex b. Then the next line has n numbers, the ith number indicates the value of the ith vertex. Values of vertices are not less than 1 and not more than 105 .
Output
For each test, at first, please output "Case #k: ", k is the number of test. Then, please output one line with n numbers (separated by spaces), representing the answer of each vertex.
Sample Input
Sample Output
Source
2015 ACM/IPCC Asia Regional Shanghai Onlineテーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=5468
1本の木をあげて、それぞれの结点に1つの値があって、今各结点を根とする子の木の中でその互质の结点の个数を求めます:もし数字をすべて1つの集合の中に置くことができるならば、集合の中で1つの数字と互质の数の个数を求めるのは裸のモビウスが反転して、しかしこの问题は木の上で、だからDFS序を考虑して、1つの点を深く検索して自分自身に遡る過程は、現在の点をルートとするサブツリー全体をちょうど遍歴しているので、答えans[x]=Σ(d|val[x])mob[d]*num[d],mob[d]はdのモビウス関数,num[d]は現在のサブツリーのdの個数(注d|val[x])であるため,最初はnlognのふるいで倍数関係のある木を前処理し,無二乗因子数で葉結点を行う必要があり,この木は約70万本の辺があり,結点xのDFSシーケンス[st,ed]に注意する.接頭辞と性質を利用して[1,ed]-[1,st]に等価にすることができ,明らかに[1,st]は深く捜す過程であり,[1,ed]は遡及する過程であるため,遡及する過程は減少し,遡及する時は加算され,最後にもう一つのwa点があり,1の場合,1と自身も相互質であることに注意する.
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 470 Accepted Submission(s): 103
Problem Description
Since both Stefan and Damon fell in love with Elena, and it was really difficult for her to choose. Bonnie, her best friend, suggested her to throw a question to them, and she would choose the one who can solve it. Suppose there is a tree with n vertices and n - 1 edges, and there is a value at each vertex. The root is vertex 1. Then for each vertex, could you tell me how many vertices of its subtree can be said to be co-prime with itself? NOTES: Two vertices are said to be co-prime if their values' GCD (greatest common divisor) equals 1.
Input
There are multiply tests (no more than 8). For each test, the first line has a number n (1≤n≤105) , after that has n−1 lines, each line has two numbers a and b (1≤a,b≤n) , representing that vertex a is connect with vertex b. Then the next line has n numbers, the ith number indicates the value of the ith vertex. Values of vertices are not less than 1 and not more than 105 .
Output
For each test, at first, please output "Case #k: ", k is the number of test. Then, please output one line with n numbers (separated by spaces), representing the answer of each vertex.
Sample Input
5 1 2 1 3 2 4 2 5 6 2 3 4 5
Sample Output
Case #1: 1 1 0 0 0
Source
2015 ACM/IPCC Asia Regional Shanghai Onlineテーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=5468
1本の木をあげて、それぞれの结点に1つの値があって、今各结点を根とする子の木の中でその互质の结点の个数を求めます:もし数字をすべて1つの集合の中に置くことができるならば、集合の中で1つの数字と互质の数の个数を求めるのは裸のモビウスが反転して、しかしこの问题は木の上で、だからDFS序を考虑して、1つの点を深く検索して自分自身に遡る過程は、現在の点をルートとするサブツリー全体をちょうど遍歴しているので、答えans[x]=Σ(d|val[x])mob[d]*num[d],mob[d]はdのモビウス関数,num[d]は現在のサブツリーのdの個数(注d|val[x])であるため,最初はnlognのふるいで倍数関係のある木を前処理し,無二乗因子数で葉結点を行う必要があり,この木は約70万本の辺があり,結点xのDFSシーケンス[st,ed]に注意する.接頭辞と性質を利用して[1,ed]-[1,st]に等価にすることができ,明らかに[1,st]は深く捜す過程であり,[1,ed]は遡及する過程であるため,遡及する過程は減少し,遡及する時は加算され,最後にもう一つのwa点があり,1の場合,1と自身も相互質であることに注意する.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const MAX = 1e5 + 5;
int const MAXM = 8e5;
int mob[MAX], p[MAX], head[MAXM], HEAD[MAX], val[MAX];
int seq[MAX << 1], ans[MAX], num[MAX];
bool noprime[MAX];
int n, cnt, dfn, CNT;
struct EDGE
{
int to, next;
}e[MAXM], E[MAX << 1];
void ADD(int u, int v)
{
E[CNT].to = v;
E[CNT].next = HEAD[u];
HEAD[u] = CNT++;
}
void Add(int u, int v)
{
e[cnt].to = v;
e[cnt].next = head[u];
head[u] = cnt++;
}
void Mobius()
{
int pnum = 0;
mob[1] = 1;
for(int i = 2; i < MAX; i++)
{
if(!noprime[i])
{
p[pnum ++] = i;
mob[i] = -1;
}
for(int j = 0; j < pnum && i * p[j] < MAX; j++)
{
noprime[i * p[j]] = true;
if(i % p[j] == 0)
{
mob[i * p[j]] = 0;
break;
}
mob[i * p[j]] = -mob[i];
}
}
}
void DFS(int u, int fa)
{
dfn ++;
seq[dfn] = u;
for(int i = HEAD[u]; i != -1; i = E[i].next)
{
int v = E[i].to;
if(v != fa)
DFS(v, u);
}
dfn ++;
seq[dfn] = -u;
}
int main()
{
Mobius();
int nnn = 0;
memset(head, -1, sizeof(head));
cnt = 0;
for(int i = 1; i <= 100000; i++)
if(mob[i])
for(int j = i; j <= 100000; j += i)
Add(j, i);
int ca = 1;
while(scanf("%d", &n) != EOF)
{
memset(HEAD, -1, sizeof(HEAD));
memset(num, 0, sizeof(num));
memset(ans, 0, sizeof(ans));
CNT = 0;
dfn = 0;
int u, v;
for(int i = 1; i < n; i++)
{
scanf("%d %d", &u, &v);
ADD(u, v);
ADD(v, u);
}
for(int i = 1; i <= n; i++)
scanf("%d", &val[i]);
DFS(1, 0);
for(int i = 1; i <= n; i++)
ans[i] = (val[i] == 1);
for(int i = 1; i <= dfn; i++)
{
if(seq[i] > 0)
{
for(int j = head[val[seq[i]]]; j != -1; j = e[j].next)
{
int v = e[j].to;
num[v] ++;
ans[seq[i]] -= mob[v] * num[v];
}
}
else
{
for(int j = head[val[-seq[i]]]; j != -1; j = e[j].next)
{
int v = e[j].to;
ans[-seq[i]] += mob[v] * num[v];
}
}
}
printf("Case #%d:", ca ++);
for(int i = 1; i <= n; i++)
printf(" %d", ans[i]);
printf("
");
}
}