HDU5599 GTW likes tree

### GTW likes tree
Time Limit: 7000/3500 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 191    Accepted Submission(s): 38

### Problem Description
GTW has a tree of n nodes, in which m nodes are special nodes. The value of node i is vi.

Dis(x,y) is defined as the greatest common divisor of the nodes in the chain between node x and node y.

Jabby(x,y) is defined as the number of special nodes in the chain between node x and node y.

You are asked to calculate the value of ans, which is defined as follow.

ans=∏i∏j=imax(1,Dis(i,j)∗min(1,jabby(i,j)))

Because ans could be very large, you only need to print ans modulo 109+7.

### Input
The first line of the input file contains an integer T, indicating the number of test cases. (T≤6)

For each test case, there are n+m+2 lines in the input file.

The first line of each test case contains a number n which indicates the number of the nodes of GTW’s tree. (1≤n≤200000)

In each line of the following n−1 lines, there are two numbers x and y which indicate that there is an undirected line between node x and node y.

The next line contains n integers, v1,v2,...,vn, in which vi indicates the value of node i. (1≤vi≤100000)

The next line contains a number m which indicates the number of special nodes.

Then in each line of the following m lines, there are an integer g which indicates that node g is a special node.

The data guarantees that the m given nodes differ from each other.

### Output
In the output file, there should be exactly T lines, each of which contains exactly one integer ans, which is defined above.

### Sample Input
```
1
2
1 2
2 2
2
1
2
```

题意：给你一棵树，给你一些关键点，让你求出关键点之间两两路径$gcd$的乘积。

这里介绍一种会被卡常但是非常具有推广性的做法。
我们可以求出$gcd=x$的路径条数，这样算什么都很方便了。
然后有一个显然的性质，考虑令每一条边$(u,v)$的权值等于$gcd(a[u],a[v])$。这样每一条路径的$gcd$和原来等价。这样我们只需要考虑边就可以了。

首先考虑所有点都是关键点。
直接求$gcd=x$不好求。考虑对于每一个$x$，求出$x|gcd$的路径条数，这样从大到小减去倍数的贡献就可以变回去。
对于每一个$x$，我们的做法是直接枚举$x$的每一个倍数，找出权值为$x$的倍数的所有边，加入图中，对每一个联通块大小求出$size\times (size-1)$求和，这个可以并查集做。
分析复杂度：一条边权值所有的因数都可以作为$x$而被这条边加入一条边。一个数最多$\sqrt V$个因数。
总的复杂度$O(n\sqrt V\alpha(n))$

不过上面被卡了，乖乖枚举$p^k$算乘积吧。

```
#prag\
ma GCC optimize("O2")
#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<cctype>
#define LL long long
using namespace std;
const int maxn = 4e5 + 5;
const int mod = 1e9 + 7;
struct edge {
	int u, v, d;
} e[maxn << 1];
int head[maxn], cnt, u, v, n, a[maxn], b[maxn];
vector<int > pos[maxn];

void read(int &x) {
	x = 0; static char c = getchar();
	while(!isdigit(c)) c = getchar();
	while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
}

int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a;
}

void Add(int &x, const int &a) {
	x += a; if(x >= mod) x -= mod;
}
void Dec(int &x, const int &a) {
	x -= a; if(x < 0) x += mod;
}
int mul(const int &a, const int &b) {
	return 1ll * a * b % mod;
}
int fpow(int a, int b) {
	int ans = 1;
	while(b) {
		if(b & 1) ans = 1ll * ans * a % mod;
		a = 1ll * a * a % mod, b >>= 1;
	}
	return ans;
}

namespace DSU {
	int fa[maxn], stk[maxn], top;
	LL siz[maxn];
	int stk2[maxn];
	LL ans;
	void init(int n) {
		for(register int i = 1; i <= n; ++i)
			fa[i] = i, siz[i] = 1;
	}
	int find(int x) {
		return fa[x] == x ? x : fa[x] = find(fa[x]);
	}
	void combine(int x, int y) {
		x = find(x), y = find(y);
		stk[++top] = x;
		stk2[top] = y;
		ans -= (siz[y]) * (siz[y] - 1);
		ans -= (siz[x]) * (siz[x] - 1);
		fa[x] = y, siz[y] += siz[x];
		ans += (siz[y]) * (siz[y] - 1);
	}
	void clear() {
		int tmp; ans = 0;
		while(top) 
			siz[stk2[top]] = 1, fa[tmp = stk[top--]] = tmp;
	}
}

LL ans[maxn];
int solve1() {
	int tmp;
	memset(ans, 0, sizeof(ans));
	ans[1] = 1ll * n * (n - 1);
	for(register int i = 2; i <= 100000; ++i) {
			for(register int j = i; j <= 100000; j += i) {
				for(register int k = pos[j].size() - 1; k >= 0; --k) {
					tmp = pos[j][k];
					DSU::combine(e[tmp].u, e[tmp].v);
				}
			}
			ans[i] = DSU::ans;
			DSU::clear();
	}
	for(register int i = 100000; i >= 1; --i) {
		for(register int j = i + i; j <= 100000; j += i)
			ans[i] -= ans[j];
	}
	int ret = 1, inv2 = fpow(2, mod - 2);
	for(register int i = 1; i <= 100000; ++i)
		ans[i] = (ans[i] / 2) % (mod - 1), ret = mul(ret, fpow(i, ans[i]));
	for(register int i = 1; i <= n; ++i)
		ret = mul(ret, a[i]);
	return ret;
}

int solve2() {
	int tmp;
	memset(ans, 0, sizeof(ans));
	for(register int i = 1; i <= 100000; ++i) {
		{
			for(register int j = i; j <= 100000; j += i) {
				for(register int k = pos[j].size() - 1; k >= 0; --k) {
					tmp = pos[j][k];
					if(b[e[tmp].u] || b[e[tmp].v]) continue;
					DSU::combine(e[tmp].u, e[tmp].v);
				}
			}
			ans[i] = DSU::ans;
			DSU::clear();
		}
	}
	for(register int i = 100000; i >= 1; --i) {
		for(register int j = i + i; j <= 100000; j += i)
			ans[i] -= ans[j];
	}
	int ret = 1, inv2 = fpow(2, mod - 2);
	for(register int i = 2; i <= 100000; ++i)
		ret = mul(ret, fpow(i, (ans[i] / 2) % (mod - 1)));
	for(register int i = 1; i <= n; ++i)
		if(!b[i]) ret = mul(ret, a[i]);
	return ret;
}

int main() {
	//freopen("tree.1.2.in", "r", stdin);
	//freopen("tree.out", "w", stdout);
	int t;
	read(t);
	while(t--) {
		read(n), cnt = 0;
		for(register int i = 1; i <= 100000; ++i)
			pos[i].clear();
		for(register int i = 1; i < n; ++i)
			read(u), read(v), e[++cnt] = (edge) {u, v};
		for(register int i = 1; i <= n; ++i)
			read(a[i]);
		for(register int i = 1; i <= n; ++i)
			read(b[i]);
		for(register int i = 1; i <= cnt; ++i)
			e[i].d = gcd(a[e[i].u], a[e[i].v]), pos[e[i].d].push_back(i);
		DSU::init(n);
		cout << mul(solve1(), fpow(solve2(), mod - 2)) << endl;
	}
	return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链