題目描述

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 6 + 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 5) and K(0 <=K < 10 6 + 3). The following line contains n numbers v i(1 <= v i < 10 6 + 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.”是指: 先按照第一個(gè)數(shù)字的大小進(jìn)行比較，若第一個(gè)數(shù)字大小相同，則按照第二個(gè)數(shù)字大小進(jìn)行比較，依次類推。
2. 若出現(xiàn)棧溢出，推薦使用C++語(yǔ)言提交，并通過以下方式擴(kuò)棧：
#pragma comment(linker,"/STACK:102400000,102400000")

題目分析

很清晰應(yīng)該使用樹分治，但是不同于一般樹分治的是這里要求我們記錄兩個(gè)點(diǎn)的位置。這就意味這不能直接套之前的模板，而必須做出一些變通。

首先，求重心、進(jìn)行分治應(yīng)該是沒有變化的，變的是對(duì)每個(gè)重心進(jìn)行處理的部分。我們要把握住問題的難點(diǎn)在于如果記錄答案的話，我們如何記錄兩個(gè)端點(diǎn)以及如何處理記錄以后去掉子樹中重復(fù)的操作。

一般的樹分治先將以重心為根的路徑全部遍歷一遍，將所有符合要求的答案保存，然后再在相同參數(shù)下遍歷子樹，將子樹中滿足條件的（說明剛才重復(fù)計(jì)算的部分）去掉。最后得到的就是答案。然而我們這里需要記錄答案，樸素的想法就是同樣將所有符合的都記錄下來（同時(shí)記錄兩個(gè)端點(diǎn)），然后再在子樹中將這些答案刪除。可是這種刪除將會(huì)非常耗費(fèi)時(shí)間，我們必須在那個(gè)暫時(shí)保存答案的集合里面找到同一對(duì)數(shù)，最快也得O(nlogn),更何況我們這個(gè)操作要進(jìn)行很多次。肯定會(huì)超時(shí)，所以我們必須換一個(gè)思路思考這個(gè)問題。

必須要?jiǎng)h除的核心關(guān)鍵在于我們?cè)诘谝淮卧L問重心的時(shí)候沒有辦法判斷是否在同一個(gè)子樹上，所以只能先加上再減去。有沒有方法能夠避免計(jì)算同一個(gè)子樹上的答案呢？

我原本的想法是每次訪問重心得到其他點(diǎn)到重心的距離前先訪問一次重心進(jìn)行染色，將每個(gè)子樹染成不同的顏色，然后再處理數(shù)據(jù)的時(shí)候再判斷是否在同一個(gè)子樹上來判斷是否是有效數(shù)據(jù)。可是題目要求記錄的是乘積等于k的字典序最小的一對(duì)端點(diǎn)。我們這樣做就必須記錄下所有的端點(diǎn)，答案可能很多，先不說存的下不，僅僅是記錄的操作估計(jì)都會(huì)超時(shí)。

不得已我上網(wǎng)看了以下其他人是怎么做的。他們的做法很巧妙，也讓我對(duì)樹分治有了更深刻的理解。

首先，我們必須扭轉(zhuǎn)將所有路徑的答案都記錄下來再進(jìn)行處理的觀念。這樣對(duì)于只是求路徑個(gè)數(shù)的可能沒有什么問題，但是對(duì)于這種需要具體得到兩個(gè)端點(diǎn)的情況會(huì)超時(shí)。所以我們必須可以在某一端點(diǎn)處直接判斷是否存在有其他端點(diǎn)可以和它湊成答案。為了達(dá)到這個(gè)效果我們用一個(gè)數(shù)組T記錄以當(dāng)前重心為根的情況下各個(gè)端點(diǎn)距離重心距離x所對(duì)應(yīng)的端點(diǎn)為T[x]，因?yàn)樽詈笮枰氖亲值湫蜃钚〉?#xff0c;所以我們保存所有T[x]中最小的就可以。然后對(duì)于每一個(gè)端點(diǎn)我們得到它的距離Dis[i]以后判斷是否有其他端點(diǎn)到樹根的距離為x使得Dis[i]*x==k，為了快速得到這個(gè)x，我們需要預(yù)處理以下乘法逆元Rev[]。則和端點(diǎn)i對(duì)應(yīng)的端點(diǎn)就應(yīng)該是T[Rev[Dis[x]]]。如果i和對(duì)應(yīng)的端點(diǎn)都存在則和當(dāng)前答案比較，確定是否更新答案。

如果不清楚什么是乘法逆元可以看一下我的這篇博客：逆元

可是這算是解決了如何存儲(chǔ)兩個(gè)端點(diǎn)的問題。但是如何消除同一個(gè)子樹中的端點(diǎn)的影響呢？我們的做法是不再像之前一樣一下遍歷所有的節(jié)點(diǎn)了，而是一個(gè)子樹一個(gè)子樹的遍歷。并且對(duì)T數(shù)組的更新放在對(duì)答案的判斷之后。這樣做的原因是訪問一個(gè)子樹的時(shí)候，他們這個(gè)字?jǐn)?shù)上的信息沒有被更新到T數(shù)組中，因此T數(shù)組中保存的就是前面的子樹的信息，也就不會(huì)出現(xiàn)訪問到同一個(gè)子樹的情況啦。

在每次開始分治，我們的T數(shù)組應(yīng)該是互相沒有聯(lián)系的，因此需要進(jìn)行清空

同時(shí)我們用一個(gè)棧來保存訪問子樹中所有節(jié)點(diǎn)的信息，先更新答案后再更新T數(shù)組。

還需要注意一點(diǎn)的是我們的信息是保存在節(jié)點(diǎn)上的，因此根節(jié)點(diǎn)的信息先不要傳遞，在更新答案的時(shí)候再算上就可以啦。

AC代碼

#pragma comment(linker,"/STACK:102400000,102400000") #include<iostream> #include<cstring> #include<cstdio> #include<climits> #include<algorithm> #include<ctime> #include<cstdlib> #include<queue> #include<set> #include<map> #include<cmath>#define RG register #define IL inlineusing namespace std; typedef long long ll; const int MAXN=2e5+5; const int MOD=1e6+3; struct edge {int to,last; }Edge[MAXN<<2]; int Last[MAXN],tot; int n,kk,SonNum[MAXN],MaxNum[MAXN],Vis[MAXN]; int root,rootx,dlen,ss,len; ll Dis[MAXN],Rev[MOD+5],Num[MAXN]; int Stack[MAXN],T[MOD+5]; int top; int ansl,ansr;IL int getint() {int x=0,sign=1; char c=getchar();while(c<'0' || c>'9'){if(c=='-') sign=-1; c=getchar();}while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+c-'0'; c=getchar();}return x*sign; } IL ll getll() {ll x=0,sign=1; char c=getchar();while(c<'0' || c>'9'){if(c=='-') sign=-1; c=getchar();}while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+c-'0'; c=getchar();}return x*sign; }IL void Init() {for(int i=0;i<=n;++i) Last[i]=0,Vis[i]=false;tot=0; ansl=ansr=INT_MAX; }IL void AddEdge(int u,int v) {Edge[++tot].to=v; Edge[tot].last=Last[u]; Last[u]=tot; }IL void Read() {for(RG int i=1;i<=n;++i) Num[i]=getll();int u,v;for(RG int i=1;i<n;i++){u=getint(); v=getint();AddEdge(u,v); AddEdge(v,u);} }void GetRoot(int x,int father) {int v;SonNum[x]=1; MaxNum[x]=1;for(int i=Last[x];i;i=Edge[i].last){v=Edge[i].to; if(v==father || Vis[v]) continue;GetRoot(v,x);SonNum[x]+=SonNum[v];if(SonNum[v]>MaxNum[x]) MaxNum[x]=SonNum[x];}MaxNum[x]=max(MaxNum[x],ss-SonNum[x]);if(rootx>MaxNum[x]) root=x,rootx=MaxNum[x]; }void GetDis(int x,int father,ll now) {ll t=now*Num[x]%MOD;Dis[x]=t; Stack[top++]=x;int v;for(RG int i=Last[x];i;i=Edge[i].last){v=Edge[i].to; if(v==father|| Vis[v]) continue;GetDis(v,x,t);} }void Update(ll x,ll y,int z) {int tmp=T[Rev[x*y%MOD]*kk%MOD];if(!tmp) return;if(z>tmp) swap(z,tmp);if(z<ansl || z==ansl&&tmp<ansr) ansl=z,ansr=tmp; }void Solve(int x) {//memset(Dis,0,sizeof(Dis));int v;T[1]=x;Vis[x]=true;for(RG int i=Last[x];i;i=Edge[i].last){dlen=0; top=0;v=Edge[i].to; if(Vis[v]) continue;GetDis(v,x,1);for(RG int j=0;j<top;++j) Update(Num[x],Dis[Stack[j]],Stack[j]);for(RG int j=0;j<top;++j) if(T[Dis[Stack[j]]]==0 || T[Dis[Stack[j]]]>Stack[j]) T[Dis[Stack[j]]]=Stack[j];}for(int i=Last[x];i;i=Edge[i].last){dlen=0; top=0;v=Edge[i].to; if(Vis[v]) continue;GetDis(v,x,1);for(int j=0;j<top;++j) T[Dis[Stack[j]]]=0;}for(int i=Last[x];i;i=Edge[i].last){v=Edge[i].to; if(Vis[v]) continue;//ans-=Count(v,Deal(x,0));ss=SonNum[v]; rootx=INT_MAX; root=0;GetRoot(v,x);Solve(root);} }IL void Work() {rootx=INT_MAX; ss=n; root=0; GetRoot(1,0); Solve(root); }IL void Write() {if(ansl==INT_MAX && ansr==INT_MAX){printf("No solution\n");}else{printf("%d %d\n",ansl,ansr);} }IL void Pre() {Rev[1]=1;for(ll i=2;i<MOD;++i)Rev[i]=(MOD-MOD/i)*Rev[MOD%i]%MOD; }int main() {Pre();while(~scanf("%d%d",&n,&kk)){Init();Read();Work();Write();}return 0; }

經(jīng)驗(yàn)總結(jié)

對(duì)于一個(gè)問題首先要抽象出來需要用那種算法進(jìn)行解決。局部的處理常常需要其他算法和數(shù)據(jù)結(jié)構(gòu)的優(yōu)化。盡可能不適用map和set等，能用數(shù)組還是盡量用數(shù)組。對(duì)數(shù)組的初始化也需要講究技巧，不能簡(jiǎn)單使用一個(gè)memset，這種做法很容易超時(shí)。

總結(jié)

以上是生活随笔為你收集整理的HDU4812-D Tree-树分治的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。