【题解】CF986E Prince's Problem(树上差分+数论性质)

题目大意：

给定你一棵树，有点权\(val_i\le 10^7\)。现在有\(m\)组询问给定参数\(x,y,w\)问你对于\((x->y)\)的路径经过的点集\(P\)，问你这个东西：

\[\prod_{u \in P} {\mathrm{gcd}(w,val_u)} \mod 1000000007
\]

考虑这样一种做法：

把询问差分成

\[\]

\[\]
考虑这类从根出发如何解决，直接遍历整棵树，对于每个节点先将自己的贡献加入某种数据结构，再递归子树，最后回溯时撤回贡献。问题就变为如何快速求\(\prod \mathrm{gcd}\)
考虑\(gcd\)的本质就是对于质因子取\(min\)且求和，而且我们知道\(1e7\)以内的质数是不多的(\(5e6\)左右)，所以直接对于每个质数开一个\(vector\)。\(vector_i\)中的下标\(j\)表示唯一分解后\(\alpha(prime[i])=j\)的树上节点有多少个。(\(\alpha\)是唯一分解后的指数)。考虑到\(\sum \alpha\)很小是\(\log\)级别，这样复杂度就是\(O(1e7+(n+m)\log 1e7)\)空间复杂度\(O((n +q)\log 1e7)\)

主要就是树上差分，还有处理\(\sum \min\{...\}\)的方法。

//@winlere

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define inv(x) (ksm((x)%mod,mod-2))

using namespace std;  typedef long long ll;

inline int qr(){

      register int ret=0,f=0;

      register char c=getchar();

      while(c<48||c>57)f|=c==45,c=getchar();

      while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();

      return f?-ret:ret;

}

const int mod=1e9+7;

int n,m;

inline int ksm(const int&ba,const int&p){

      int ret=1;

      for(int t=p,b=ba%mod;t;t>>=1,b=1ll*b*b%mod)

	    if(t&1) ret=1ll*ret*b%mod;

      return ret;

}

vector< vector<int> > s;

namespace PRE{

      const int maxn=1e7+5;

      int rank[maxn],usd[maxn],arc[maxn],Min[maxn];

      vector<int> pr;

      inline void pre(const int&n){

	    usd[1]=1; Min[1]=10;

	    for(int t=2;t<=n;++t){

		  if(!usd[t]) Min[t]=t,pr.push_back(t),rank[t]=pr.size(),arc[rank[t]]=t;

		  for(auto f:pr){

			if(1ll*f*t>n)break;

			usd[f*t]=1;

			Min[f*t]=f;

			if(t%f==0)break;

		  }

	    }

	    s.resize(pr.size()+1);

      }

}

namespace TREE{

      const int maxn=1e5+5;

      int d[maxn];

      vector<int> e[maxn];

      vector<int> q[maxn];

      int W[maxn],ans[maxn],w[maxn];

      inline void add(const int&fr,const int&to){

	    e[fr].push_back(to);

	    e[to].push_back(fr);

      }

      int son[maxn],top[maxn],r[maxn],siz[maxn];

      void pre(const int&now,const int&last){

	    siz[now]=1;

	    r[now]=last;

	    d[now]=d[last]+1;

	    for(auto t:e[now])

		  if(t^last) {

			pre(t,now); siz[now]+=siz[t];

			if(siz[now]>siz[son[now]]) son[now]=t;

		  }

      }

      void qaq(const int&now,const int&last){

	    top[now]=last;

	    if(son[now]) qaq(son[now],last);

	    for(auto t:e[now])

		  if((t^r[now])&&(t^son[now]))

			qaq(t,t);

      }

      inline void init(const int&n){pre(1,0);qaq(1,0);}

      inline int lca(int u,int v){

	    if(d[u]<d[v])swap(u,v);

	    while(top[u]^top[v]){

		  if(d[top[u]]<d[top[v]]) swap(u,v);

		  u=r[top[u]];

	    }

	    return d[u]<d[v]?u:v;

      }

      inline void addq(const int&x,const int&y,const int&id,const int&w){

	    ans[id]=1;

	    q[x].push_back(id);

	    q[y].push_back(id);

	    q[lca(x,y)].push_back(-id);

	    W[id]=w;

      }

}

namespace sol{

      const int maxn=1e5+5;

      using namespace TREE;

      using PRE::rank;

      using PRE::Min;

      inline void add(const int&now,const int&tag){

	    //now 是节点编号 tag 是操作类型

	    int k=w[now],cnt=0;

	    static int a[23],p[23];

	    while(k>1){

		  int f=Min[k];

		  a[++cnt]=0;

		  p[cnt]=f;

		  while(k%f==0) k/=f,++a[cnt];

	    }

	    for(int t=1;t<=cnt;++t){

		  if(((int)s[rank[p[t]]].size())<=1+a[t])

			s[rank[p[t]]].resize(a[t]+2);

		  s[rank[p[t]]][a[t]]+=tag;

	    }

      }

      inline void que(const int&now,const int&id){

	    //now 是询问编号

	    int k=W[now>0?now:-now],cnt=0,ret=1;

	    static int a[23],p[23];

	    while(k>1){

		  int f=Min[k];

		  a[++cnt]=0;

		  p[cnt]=f;

		  while(k%f==0) k/=f,++a[cnt];

	    }

	    for(int t=1;t<=cnt;++t)

		  for(int i=1,ed=s[rank[p[t]]].size();i<ed;++i)

			ret=1ll*ret*ksm(p[t],1ll*s[rank[p[t]]][i]*min(a[t],i)%(mod-1))%mod;

	    if(now<0)  ans[-now]=1ll*ans[-now]*inv(ret)%mod*inv(ret)%mod*__gcd(W[-now],w[id])%mod;

	    else  ans[now]=1ll*ans[now]*ret%mod;

      }

      void dfs(const int&now,const int&last){

	    add(now,1);

	    for(auto t:q[now]) que(t,now);

	    for(auto t:e[now])

		  if(t^last) dfs(t,now);

	    add(now,-1);

      }

}

int main(){

      PRE::pre(1e7);

      n=qr();

      for(int t=2;t<=n;++t) TREE::add(qr(),qr());

      for(int t=1;t<=n;++t) TREE::w[t]=qr();

      TREE::init(n);

      m=qr();

      for(int t=1,t1,t2,t3;t<=m;++t) {

	    t1=qr(); t2=qr(); t3=qr();

	    TREE::addq(t1,t2,t,t3);

      }

      sol::dfs(1,0);

      for(int t=1;t<=m;++t) printf("%d\n",TREE::ans[t]);

      return 0;

}

巴特西

【题解】CF986E Prince's Problem(树上差分+数论性质)

【题解】CF986E Prince's Problem(树上差分+数论性质)

最新文章

热门文章