HDU D Tree [点分治]

时间：2024-11-23 15:07:55

传送门

题意：找路径积$\mod 1e6+3 = k$的字典序最小点对

作为一个点分治蒟蒻，写这道题花了两节课....

显然只要开一个桶$c[i]$记录当前路径积为$i$的最小点

然后处理一个子树时一个个子树遍历更新答案再更新$c$就行了

最后再把$c$复原

可以用一个栈记下更改过的$c$，但貌似比在遍历一遍树更慢？

然后注意更新和复原$c[w[u]]$

好了回教室上数学课啦

#pragma comment(linker,"/STACK:102400000,102400000")

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const int N=1e5+,M=1e6+,P=1e6+,INF=1e9;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n;ll k,w[N];

struct edge{

    int v,ne;

}e[N<<];

int h[N],cnt;

inline void ins(int u,int v){

    cnt++;

    e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;

    cnt++;

    e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt;

}

int inv[M];

void iniInv(){

    inv[]=;

    for(int i=;i<P;i++)

        inv[i]=(ll)(P-P/i)*inv[P%i]%P;

}

int size[N],f[N],vis[N],root,allSize;

void dfsRt(int u,int fa){

    size[u]=;f[u]=;

    for(int i=h[u];i;i=e[i].ne){

        int v=e[i].v;

        if(vis[v]||v==fa) continue;

        dfsRt(v,u);

        size[u]+=size[v];

        f[u]=max(f[u],size[v]);

    }

    f[u]=max(f[u],allSize-size[u]);

    if(f[u]<f[root]) root=u;

}

int c[M],ans[];

int st[N],top;

void dfsDee(int u,int fa,int now){

    if(!c[now]) c[now]=u;//,st[++top]=now;

    else c[now]=min(c[now],u);

    for(int i=h[u];i;i=e[i].ne){

        int v=e[i].v;

        if(!vis[v]&&v!=fa) dfsDee(v,u,now*w[v]%P);

    }

}

void dfsAns(int u,int fa,int now){

    int x=c[k*inv[now]%P],y=u;

    if(x){

        if(x>y) swap(x,y);

        if(x<ans[]||(x==ans[]&&y<ans[])) ans[]=x,ans[]=y;

    }

    for(int i=h[u];i;i=e[i].ne){

        int v=e[i].v;

        if(!vis[v]&&v!=fa) dfsAns(v,u,now*w[v]%P);

    }

}

void dfsRec(int u,int fa,int now){

    c[now]=;

    for(int i=h[u];i;i=e[i].ne){

        int v=e[i].v;

        if(!vis[v]&&v!=fa) dfsRec(v,u,now*w[v]%P);

    }

}

void dfsSol(int u){

    vis[u]=;

    c[w[u]]=u;

    for(int i=h[u];i;i=e[i].ne){

        int v=e[i].v;

        if(!vis[v]){

            dfsAns(v,u,w[v]);

            dfsDee(v,u,w[u]*w[v]%P);

        }

    }

    //while(top) c[st[top]]=0,top--;

    for(int i=h[u];i;i=e[i].ne) if(!vis[e[i].v]) dfsRec(e[i].v,u,w[u]*w[e[i].v]%P);

    c[w[u]]=;

    for(int i=h[u];i;i=e[i].ne){

        int v=e[i].v;

        if(!vis[v]){

            root=;allSize=size[v];

            dfsRt(v,);

            dfsSol(root);

        }

    }

}

int main(){

    freopen("in","r",stdin);

    iniInv();

    while(scanf("%d%lld",&n,&k)!=EOF){

        memset(vis,,sizeof(vis));

        cnt=;memset(h,,sizeof(h));

        memset(c,,sizeof(c));

        for(int i=;i<=n;i++) w[i]=read();

        for(int i=;i<=n-;i++) ins(read(),read());

        ans[]=ans[]=INF;

        f[]=INF;

        root=;allSize=n;

        dfsRt(,);

        dfsSol(root);

        if(ans[]!=INF) printf("%d %d\n",ans[],ans[]);

        else puts("No solution");

    }

}

相关文章