hdu 4812 D Tree

hdu 4812 D Tree

​​ Problem Description There is a skyscraping tree standing on the playground of Nanjing University of Science and Technology. On each branch of the tree is an integer (The tree can be treated as a connected graph with N vertices, while each branch can be treated as a vertex). Today the students under the tree are considering a problem: Can we find such a chain on the tree so that the multiplication of all integers on the chain (mod 106 + 3) equals to K? Can you help them in solving this problem?

Input There are several test cases, please process till EOF. Each test case starts with a line containing two integers N(1 <= N <= 105) and K(0 <=K < 106 + 3). The following line contains n numbers vi(1 <= vi < 106 + 3), where vi indicates the integer on vertex i. Then follows N - 1 lines. Each line contains two integers x and y, representing an undirected edge between vertex x and vertex y.

Output For each test case, print a single line containing two integers a and b (where a < b), representing the two endpoints of the chain. If multiply solutions exist, please print the lexicographically smallest one. In case no solution exists, print “No solution”(without quotes) instead. For more information, please refer to the Sample Output below.

Sample Input 5 60 2 5 2 3 3 1 2 1 3 2 4 2 5 5 2 2 5 2 3 3 1 2 1 3 2 4 2 5

Sample Output 3 4 No solution

Hint 1. “please print the lexicographically smallest one.”是指: 先按照第一个数字的大小进行比较，若第一个数字大小相同，则按照第二个数字大小进行比较，依次类推。 2. 若出现栈溢出，推荐使用C++语言提交，并通过以下方式扩栈： #pragma comment(linker,”/STACK:102400000,102400000”)

Source 2013ACM/ICPC亚洲区南京站现场赛——题目重现 我真是zz 这水题调了一天.. 考虑做一个链的前缀和 然后每次都存下来 记录下标为这个乘积的逆元的情况的最小节点 然后每次先做后插入 最后再清空即可

#include#include#include#include#define ll long longusing namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();} while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x*f;}const int mod=1e6+3;const int N1=1100000;const int N=1e5+10;const int inf=0x3f3f3f3f;bool visit[N];int h[N],dis[N],inv[N1],ans1,ans2,v[N],sum,f[N],n,k,num,root,size[N],tmp[mod],K;struct node{ int y,next;}data[N<<1];inline void get_root(int x,int fa){ size[x]=1;f[x]=0; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (y==fa||visit[y]) continue; get_root(y,x);size[x]+=size[y];f[x]=max(f[x],size[y]); }f[x]=max(sum-size[x],f[x]); if(f[x]y) swap(x,y); if (ans1>x) ans1=x,ans2=y; else if (ans1==x&&ans2>y) ans1=x,ans2=y;}inline void dfs(int x,int fa){ if(tmp[dis[x]]!=inf) get(x,tmp[dis[x]]); for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if(y==fa||visit[y]) continue; dis[y]=(ll)dis[x]*v[y]%mod;dfs(y,x); }}inline void insert1(int x,int fa){ tmp[(ll)inv[dis[x]]*K%mod]=min(tmp[(ll)inv[dis[x]]*K%mod],x); for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (y==fa||visit[y]) continue;insert1(y,x); }}inline void clear(int x,int fa){ tmp[(ll)inv[dis[x]]*K%mod]=inf; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if(y==fa||visit[y]) continue;clear(y,x); }}inline void solve(int x){ visit[x]=1;K=(ll)k*inv[v[x]]%mod;tmp[K]=x; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (visit[y]) continue; if (size[y]>size[x]) size[y]=sum-size[x]; dis[y]=v[y];dfs(y,x);insert1(y,x); }tmp[K]=inf; for (int i=h[x];i;i=data[i].next){int y=data[i].y;if (visit[y]) continue;clear(y,x);} for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (visit[y]) continue; sum=size[y];root=0;get_root(y,x);solve(root); }}int main(){ freopen("hdu4812.in","r",stdin); inv[0]=inv[1]=1;memset(tmp,0x3f,sizeof(tmp)); for (int i=2;i<=1e6+2;++i) inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod; while(~scanf("%d%d",&n,&k)){ for (int i=1;i<=n;++i) v[i]=read()%mod; memset(h,0,sizeof(h));num=0;memset(visit,0,sizeof(visit));ans1=ans2=inf; for (int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。