HDU 4812 D Tree 树分治+逆元+hash新姿势

题意:

给定n个点的树 K

下面n个数是点权

下面n-1行给出树边。

问:

是否存在一条路径使得路径上点权积 % mod = K

若存在则输出路径的两端。

若存在多条路径则输出字典序最小的一条。

思路:

按树重心分治。

分成路径是否经过树重心。

然后用力码。。

has[x] = u;

表示乘积为x 对应的点是u

但这样has就不能用计数器来优化清空。

所以用2个数组: has[x] = cnt; has_id[x] = u;

这样has里存的是乘积为x是否存在。has_id[x] 来记录点。

#pragma comment(linker, "/STACK:10240000000000,10240000000000") #include #include #include #include #include #include using namespace std; const int inf = 10000000; typedef pair pii; typedef long long ll; const int mod = 1000000+3; int ni[mod]; void quick(int x){ int ans = 1, tmp = x, y = mod-2; while(y){ if(y&1) ans = (ll)ans * (ll)x % (ll)mod; x = (ll)x*(ll)x%(ll)mod; y>>=1; } ni[tmp] = ans; } template inline bool rd(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; while(c!='-'&&(c'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c inline void pt(T x) { if (x 9) pt(x/10); putchar(x%10+'0'); } #define N 100005 pii ans; void updata(int x, int y){ if(x>y)swap(x,y); if(ans.first > x || ans.first==x && ans.second > y) ans = pii(x,y); } struct Edge{ int to, nex; }edge[N

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:hdu 4871 树的分治+最短路记录路径
下一篇:BNUOJ34973Liserious战队
相关文章

UVA 11765 Component Placement 网

图文推荐

HDU 4812 D Tree 树分治+逆元+hash新姿势
ZOJ 3640 Help Me
HDU 4812 D Tree 树分治+逆元+hash新姿势
CF 518C(Anya and
HDU 4812 D Tree 树分治+逆元+hash新姿势
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2015-03-12 人气:1
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.076 (s). 10 q(s)