题目链接 http://uoj.ac/problem/192
暑期课第二天
树上问题进阶
具体内容看笔记博客吧
题意
n个节点的树T 边有边权w 求满足(u, v)上所有边权乘积为完全平方数的路径有多少条
看到“所有边权乘积为完全平方数” 想到完全平方数的特殊性
就是分解质因数后 质因数指数都为偶数
然后就想到分解边权质因数＋判质路径边权奇偶性
后者由于奇数偶数的和的规律 可以使用抑或
偶就表示为0 奇就表示为一
那么如何存储呢？
状压？
空间之大 状压压不下
所以hash
对每一个要用的质数 取一个 [1, 2 ^ 64] 的随机数
出现一次就抑或一次即可
然后。。。
题意
n个节点的树T 边有边权w 求满足(u, v)上所有边权抑或和为0的路径有多少条
前缀和最常用的两种 一是累加和 二是抑或和
明显可以使用前缀和
又由于 a ^ a = 0
对于一条路径 （路径两端点的lca） 到 （根节点）的那一段抑或两次没啦
所以如果(u, v)上所有边权抑或和为0
那么他们的抑或前缀和相等
以下附莫名被ex扣下3分的辣鸡代码
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <map>
using namespace std;
const int N = 2e5 + ;
const int M = 1e4 + ; int n, m;
struct Edge{
int u, v;
long long w;
int next;
}edge[N << ];
int esize, head[N];
long long p[M + ], ps;
bool np[M];
long long num[N];
map<int, long long> rf; inline void addedge(int x, int y, long long z){
edge[++esize] = (Edge){x, y, z, head[x]};
head[x] = esize;
} inline void p_cal(){
for(int i = ; i < M; i++){
if(!np[i]) p[++ps] = i;
for(int j = ; j <= ps && i * p[j] < M; j++){
np[i * p[j]] = ;
if(!(i % p[j])) break;
}
}
} inline void build(int x, int fa){
for(int i = head[x]; i != -; i = edge[i].next){
int v = edge[i].v;
if(v == fa) continue;
num[v] = num[x] ^ edge[i].w;
build(v, x);
}
} int main(){
srand(time(NULL));
scanf("%d", &n);
p_cal();
for(long long i = ; i <= ps; i++)
rf[p[i]] = ((long long)rand() << ) + rand();
//rd续命法
long long res;
int x, y, z;
for(int i = ; i <= n; i++) head[i] = -;
for(int i = , x, y, z; i < n; i++){
scanf("%d%d%d", &x, &y, &z);
res = ;
int tmp = z;
for(int j = ; j <= ps && p[j] * p[j] <= tmp; j++)
while(!(z % p[j]))
res ^= rf[p[j]], z /= p[j];
if(z != ) {
if(!rf[z])
rf[z] = ((long long)rand() << ) + rand();
res ^= rf[z];
}
addedge(x, y, res); addedge(y, x, res);
} build(, -);
sort(num + , num + n + );
long long ans = ;
for(int i = , j; i <= n; i = j){
j = i;
while(num[j] == num[i] && j <= n) j++;
ans += (long long)(j - i) * (j - i - );
}
printf("%lld", ans);
return ;
}