给一颗树，边有边权。求经过的边权积为完全平方数的路径条数。
\(n<1e5,a_i<1e8\)
emm
可以看出要用点分治。
可是桶不好开。
所以要考虑转换。
我们可以将任意一个数X这样表示。
\(X = p_1^{a_1}\* p_2^{a_2} \* p_3^{a_3}\) ......
\(p\) 为质数。
然后我们给所有\(p_i\) 赋一个随机值\(h(p_i)\)。
定义 \(F(X)\) 为所有 \(a_i为奇数的h(p_i)的异或和\)
所以，我们可以得到。
当且仅当 \(F(x) = 0\) 时，\(x\) 为完全平方数。
所以我们可以把 \(A,B\) 两数的积用 \(F(A)\oplus F(B)\) 表示，因为我们仅需要知道一个数是否为完全平方数。
然后这题就完了。
好吧，还有一些细节。
比如 \(h(p_i)\) 的随机值要是 \(long~long\) 范围的。这样才能保证正确性。
还有，因为 \(a_i<1e8\) 不能用线性筛，所以我们要筛出 \(1e4\) 以内的质数，然后对所有数用 \(\frac {\sqrt a_i}{\ln n}\) 的复杂度算出 \(F(a_i)\) 。
还有一点很重要，桶不能用 \(map\) ，只能用 \(hash\) 。
先上一份自己打的，但是被 \(hack\) 数据卡T了的代码：
#pragma GCC optimize(2) #pragma G++ optimize(2) #pragma GCC optimize(3) #pragma G++ optimize(3) #include <bits/stdc++.h> using namespace std; #define fst first #define snd second #define SZ(u) ((int) (u).size()) #define ALL(u) (u).begin(), (u).end() template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } template<typename T> inline T read() { register T sum(0), fg(1); register char ch(getchar()); for(; !isdigit(ch); ch = getchar()) if(ch == '-') fg = -1; for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) - 48 + ch; return sum * fg; } typedef long long LL; typedef pair<int, LL> pii; const int Maxn = 1e5 + 10, Maxv = 1e4 + 10, mod = 2333333; vector <pii> Map[Maxn]; unordered_map <LL, LL> mp,book; int pre[Maxn], top, Top, siz[Maxn], n; bool vis[Maxn],bk[Maxn + 10]; long long p[Maxn] ,del[Maxn], pre_rand[Maxn + 10], stk[Maxn], ans; LL Rand(){ int res = rand(),res2 = rand(); LL tmp = 1ll * res * res2; while(tmp <= 0) { if(res > res2) swap(res,res2); res = rand(); tmp = 1ll * res * res2; } return tmp; } vector<pii> h[mod + 10]; int ask(LL number){ int now = number % mod; for (int i = h[now].size() - 1;i >= 0; --i){ if(h[now][i].snd == number) return h[now][i].fst; } return 0; } void add(LL number, int d){ int now = number % mod; bool fl = 1; for (int i = h[now].size() - 1;i >= 0; --i){ if(h[now][i].snd == number) h[now][i].fst += d,fl = 0; } if(fl)h[now].push_back((pii){d,number}); } void init(){ srand(19260817); for (int i = 2;i <= Maxv; ++i){ if(!bk[i]){ pre[++Top] = i; pre_rand[Top] = Rand(); for (int j = i << 1; j <= Maxv; j += i) bk[j] = 1; } } } void div_siz(int now, int pa){ siz[now] = 1; for (int i = Map[now].size() - 1; i >= 0; --i){ int nxt = Map[now][i].fst; if(vis[nxt] || nxt == pa)continue; div_siz(nxt, now); siz[now] += siz[nxt]; } } int div_rt(int now,int pa, int tot_siz){ bool fg = 1; for (int i = Map[now].size() - 1; i >= 0; --i){ int nxt = Map[now][i].fst; if(vis[nxt] || nxt == pa)continue; int p = div_rt(nxt,now,tot_siz); if(p) return p; if((siz[nxt] << 1) > tot_siz) fg = 0; } if((tot_siz - siz[now] << 1) > tot_siz) fg = 0; if(fg) return now; return 0; } LL get_p(int number){ LL res = 0; for (int i = 1; i <= Top && pre[i] <= number; ++i){ while(number % pre[i] == 0){ res ^= pre_rand[i]; number /= pre[i]; } } if (number > 1){ if (!mp[number]){ mp[number] = Rand(); } res ^= mp[number]; } return res; } void get_dis(int now, int pa){ stk[++top] = p[now]; for (int i = Map[now].size() - 1; i >= 0; --i){ int nxt = Map[now][i].fst; if(vis[nxt] || nxt == pa)continue; p[nxt] = p[now] ^ Map[now][i].snd; get_dis(nxt, now); } } void calc(int now){ int tot = 0; for (int i = Map[now].size() - 1; i >= 0; --i){ int nxt = Map[now][i].fst; if(vis[nxt]) continue; top = 0; p[nxt] = Map[now][i].snd; get_dis(nxt, now); for (int j = 1; j <= top; ++j){ ans += ask(stk[j]); } for (int j = 1; j <= top; ++j) add(stk[j], 1), del[++tot] = stk[j]; } for (int i = 1; i <= tot; ++i) add(del[i], -1); } void div_solve(int now){ div_siz(now, 0), now = div_rt(now, 0, siz[now]), calc(now); vis[now] = 1; for (int i = Map[now].size() - 1; i >= 0; --i){ int nxt = Map[now][i].fst; if(!vis[nxt]) div_solve(nxt); } } int main() { #ifndef ONLINE_JUDGE freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); #endif n = read<int>(); init(); for (int i = 1; i < n; ++i){ int x = read<int>(), y = read<int>(), w = read<int>(); LL w0 = get_p(w); Map[x].push_back((pii){y, w0}); Map[y].push_back((pii){x, w0}); } add(0,1); div_solve(1); printf("%lld\n",2ll * ans); return 0; }这份代码，卡了半年常，就是卡不过。
后来把手写哈希换成hash_table就过了。
感谢fatesky大佬的帮助！！！
#include <bits/stdc++.h> using namespace std; #define fst first #define snd second #define SZ(u) ((int) (u).size()) #define ALL(u) (u).begin(), (u).end() template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } template<typename T> inline T read() { register T sum(0), fg(1); register char ch(getchar()); for(; !isdigit(ch); ch = getchar()) if(ch == '-') fg = -1; for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) - 48 + ch; return sum * fg; } typedef long long LL; typedef pair<int, LL> pii; const int Maxn = 1e5 + 10, Maxv = 1e4 + 10, mod = 2333333; vector <pii> Map[Maxn]; map <LL, LL> mp,book; int pre[Maxn], top, Top, siz[Maxn], n; bool vis[Maxn],bk[Maxn + 10]; long long p[Maxn],del[Maxn], pre_rand[Maxn + 10], stk[Maxn], ans; LL Rand(){ int res = rand(),res2 = rand(); LL tmp = 1ll * res * res2; while(tmp <= 0) { if(res > res2) swap(res,res2); res = rand(); tmp = 1ll * res * res2; } return tmp; } #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; namespace DIV { cc_hash_table<LL, int> H; void init(){ srand(19260817); for (int i = 2;i <= Maxv; ++i){ if(!bk[i]){ pre[++Top] = i; pre_rand[Top] = Rand(); for (int j = i << 1; j <= Maxv; j += i) bk[j] = 1; } } } void div_siz(int now, int pa){ siz[now] = 1; for (int i = Map[now].size() - 1; i >= 0; --i){ int nxt = Map[now][i].fst; if(vis[nxt] || nxt == pa)continue; div_siz(nxt, now); siz[now] += siz[nxt]; } } int div_rt(int now,int pa, int tot_siz){ #define p zjmsb bool fg = 1; for (int i = Map[now].size() - 1; i >= 0; --i){ int nxt = Map[now][i].fst; if(vis[nxt] || nxt == pa)continue; int p = div_rt(nxt,now,tot_siz); if(p) return p; if((siz[nxt] << 1) > tot_siz) fg = 0; } if((tot_siz - siz[now]) * 2 > tot_siz) fg = 0; if(fg) return now; return 0; #undef p } LL get_p(int number){ LL res = 0; for (int i = 1; i <= Top && pre[i] <= number; ++i){ while(number % pre[i] == 0){ res ^= pre_rand[i]; number /= pre[i]; } } if (number > 1){ if (!mp[number]) mp[number] = Rand(); res ^= mp[number]; } return res; } void get_dis(int now, int pa){ stk[++top] = p[now]; for (int i = Map[now].size() - 1; i >= 0; --i){ int nxt = Map[now][i].fst; if(vis[nxt] || nxt == pa)continue; p[nxt] = p[now] ^ Map[now][i].snd; get_dis(nxt, now); } } void calc(int now){ H.clear(); ++H[0]; int tot = 0; for (int i = Map[now].size() - 1; i >= 0; --i){ int nxt = Map[now][i].fst; if(vis[nxt]) continue; top = 0; p[nxt] = Map[now][i].snd; get_dis(nxt, now); for (int j = 1; j <= top; ++j) if(H.find(stk[j]) != H.end()) ans += H[stk[j]]; for (int j = 1; j <= top; ++j) ++H[stk[j]]; } } void div_solve(int now){ div_siz(now, 0), now = div_rt(now, 0, siz[now]), calc(now); vis[now] = 1; for (int i = Map[now].size() - 1; i >= 0; --i){ int nxt = Map[now][i].fst; if(!vis[nxt]) div_solve(nxt); } } } using namespace DIV; int main() { #ifndef ONLINE_JUDGE freopen("zjm.in", "r", stdin); freopen("zjm.out", "w", stdout); #endif n = read<int>(); init(); for (int i = 1; i < n; ++i){ int x = read<int>(), y = read<int>(), w = read<int>(); LL w0 = get_p(w); Map[x].emplace_back(y, w0); Map[y].emplace_back(x, w0); } div_solve(1); printf("%lld\n",2ll * ans); return 0; }转载于:https://www.cnblogs.com/LZYcaiji/p/10397871.html
相关资源：JAVA上百实例源码以及开源项目