HDU 4812 D Tree 树分治+逆元+hash新姿势 - c++编程基础

TOP

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

2015-07-20 17:33:19 来源: 作者: 【大中小】浏览:3次

Tags：HDU 4812 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<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } template 
          
            inline void pt(T x) { if (x <0) { putchar('-'); x = -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<<1]; int head[N], edgenum; void init(){memset(head,-1,sizeof head); edgenum = 0;} void add(int u, int v){ Edge E = {v,head[u]}; edge[edgenum] = E; head[u] = edgenum++; } int a[N], K, mul[N]; int n, siz[N]; int s[N], id[N], top; int has[mod], has_id[mod], tim; bool vis[N]; void add_hash(int u, int multi_ans){ if(has[multi_ans] == tim) has_id[multi_ans] = min(has_id[multi_ans], u); else { has[multi_ans] = tim; has_id[multi_ans] = u; } } int wval, wroot; void getroot(int u, int fa){ siz[u] = 1; int maxv = 0; for(int i = head[u]; ~i; i = edge[i].nex){ int v = edge[i].to; if(v == fa || vis[v])continue; getroot(v, u); siz[u] += siz[v]; maxv = max(maxv, siz[v]); } maxv = max(maxv, siz[0] - siz[u]); if(maxv < wval)wval = maxv, wroot = u; } int find_root(int u, int fa){ //找到子树的重心 wval = 1000000; getroot(u, fa); return wroot; } void multi(int u, int fa){ mul[u] = ((ll)a[u]*(ll)mul[fa])%(ll)mod; siz[u] = 1; s[top] = mul[u]; id[top++] = u; for(int i = head[u];~i;i=edge[i].nex){ int v = edge[i].to; if(v == fa || vis[v])continue; multi(v, u); siz[u] += siz[v]; } } void solve(int u){ tim++; mul[u] = 1; vis[u] = 1; for(int i = head[u]; ~i; i = edge[i].nex){ int v = edge[i].to; if(vis[v])continue; top = 0; multi(v, u); for(int i = 0; i < top; i++) { if(K == (ll)s[i]*(ll)a[u]%(ll)mod) updata(u, id[i]); int x = (ll)K * (ll)ni[ (ll)s[i] * (ll)a[u] % (ll)mod ] % (ll)mod; if(has[x] == tim) updata(id[i], has_id[x]); } for(int i = 0; i < top; i++) { add_hash(id[i], s[i]); } } for(int i = head[u];~i;i=edge[i].nex){ int v = edge[i].to; if(vis[v])continue; siz[0] = siz[v]; solve(find_root(v, u)); } } void input(){ init(); for(int i = 1; i <= n; i++)rd(a[i]); for(int i = 1, u, v; i < n; i++) { rd(u); rd(v); add(u,v); add(v,u); } } int main() { tim = 0; memset(has, 0, sizeof has); for(int i = 0; i < mod; i++) quick(i); while(rd(n) && rd(K)) { input(); ans.first = inf; memset(vis, 0, sizeof vis); siz[0] = n; solve(find_root(1,1)); if(ans.first == inf)puts("No solution"); else { pt(ans.first); putchar(' '); pt(ans.second); putchar('\n'); } } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：C++中使用Json的方法	下一篇：HDU 3829 Cat VS Dog

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: