hdu 4812 D Tree(树的点分治)

D Tree

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 102400/102400 K (Java/Others)
Total Submission(s): 1687 Accepted Submission(s): 263

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 10⁶ + 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 <= 10⁵) and K(0 <=K < 10⁶ + 3). The following line contains n numbers v_i(1 <= v_i < 10⁶ + 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

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亚洲区南京站现场赛——题目重现

Recommend

liuyiding | We have carefully selected several similar problems for you: 5068 5067 5065 5064 5062

题意：

给你一个n(1e5)个结点的数。每一个结点有个权值v(1 <= v_i < 10⁶ + 3).问你是否存在一条路径u->v。

使得路径上的结点的乘积为k(0 <=K < 10⁶ + 3).有多解输出字典序最小的解。

思路：

先找树的重心。再按树的重心分治。计算子树全部结点到分治重心路径权值的乘积val。再查询hash表看有没有k*inv[val]存在。有就更新答案。分治完一颗子树后再更新hash表。

具体见代码：

#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
const int mod=1e6+3;
typedef long long ll;
ll inv[mod+10];
int val[maxn],ms[maxn],son[maxn],vis[maxn],cnt,kv;
int mp[mod+10],use[mod+10],ptr,pos,ans1,ans2;
struct node
{
    int v;
    node *next;
} ed[maxn<<1],*head[maxn];
void adde(int u,int v)
{
    ed[cnt].v=v;
    ed[cnt].next=head[u];
    head[u]=&ed[cnt++];
}
void dfs(int fa,int u)
{
    son[u]=1;
    ms[u]=0;
    for(node *p=head[u];p!=NULL;p=p->next)
    {
        if(p->v==fa||vis[p->v])
            continue;
        dfs(u,p->v);
        son[u]+=son[p->v];
        ms[u]=max(ms[u],son[p->v]);
    }
}
void findroot(int fa,int u,int all)
{
    ms[u]=max(ms[u],all-son[u]);
    if(ms[u]<ms[pos])
        pos=u;
    for(node *p=head[u];p!=NULL;p=p->next)
    {
        if(p->v==fa||vis[p->v])
            continue;
        findroot(u,p->v,all);
    }
}
void getroot(int u)
{
    dfs(-1,u);
    pos=u;
    findroot(-1,u,son[u]);
}
void cal(int fa,int u,int mc)//计算答案
{
    mc=(ll)mc*val[u]%mod;
    int op=(ll)kv*inv[mc]%mod,a,b;
    if(mp[op])
    {
        a=u,b=mp[op];
        if(a>b)
            swap(a,b);
        if(a<ans1)
            ans1=a,ans2=b;
        else if(a==ans1&&b<ans2)
            ans2=b;
    }
    for(node *p=head[u];p!=NULL;p=p->next)
    {
        if(p->v==fa||vis[p->v])
            continue;
        cal(u,p->v,mc);
    }
}
void update(int fa,int u,int mc)//更新hash表
{
    mc=(ll)mc*val[u]%mod;
    if(!mp[mc])
        use[ptr++]=mc,mp[mc]=u;
    else
        mp[mc]=min(mp[mc],u);
    for(node *p=head[u];p!=NULL;p=p->next)
    {
        if(p->v==fa||vis[p->v])
            continue;
        update(u,p->v,mc);
    }
}
void solve(int u)//每次处理一颗子树
{
    int root,i;
    getroot(u);
    root=pos;
    mp[val[root]]=root;
    vis[root]=1,ptr=0;
    for(node *p=head[root];p!=NULL;p=p->next)
    {
        if(vis[p->v])
            continue;
        cal(root,p->v,1);//计算子树路径
        update(root,p->v,val[root]);
    }
    for(i=0;i<ptr;i++)
        mp[use[i]]=0;
    mp[val[root]]=0;
    for(node *p=head[root];p!=NULL;p=p->next)
    {
        if(vis[p->v])
            continue;
        solve(p->v);
    }
}
int main()
{
    int n,i,u,v;
    inv[1]=1;
    for(i=2;i<mod;i++)//预处理逆元
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    while(~scanf("%d%d",&n,&kv))
    {
        for(i=1;i<=n;i++)
            scanf("%d",&val[i]);
        memset(head,0,sizeof head);
        memset(vis,0,sizeof vis);
        cnt=0;
        for(i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            adde(u,v);
            adde(v,u);
        }
        ans1=ans2=INF;
        solve(1);
        if(ans1!=INF)
            printf("%d %d
",ans1,ans2);
        else
            printf("No solution
");
    }
    return 0;
}