題目大意：

EZ同學(xué)家里非常富有，但又極其的謙虛，說(shuō)話(huà)又好聽(tīng)，是個(gè)不可多得的人才。
EZ常常在假期環(huán)游世界，他準(zhǔn)備去N（N<=100000）個(gè)國(guó)家之多，一些國(guó)家有航線(xiàn)連接，由于EZ同學(xué)有一定的強(qiáng)迫癥，任意兩個(gè)國(guó)家之間都能通過(guò)航路直接或間接到達(dá)，并且這樣的路徑僅有一種。（簡(jiǎn)單來(lái)說(shuō)，這些國(guó)家構(gòu)成了一棵樹(shù)）
由于EZ是C國(guó)人，因此將C國(guó)（1號(hào)國(guó)家）作為整棵樹(shù)的根
每個(gè)國(guó)家有一個(gè)旅游熱度A[i]和影響力D[i]。由于目的地有點(diǎn)多，為了避免選擇困難癥，他給每個(gè)國(guó)家設(shè)置了一個(gè)向往值F[i]，它等于所有的A[j]之和，滿(mǎn)足i國(guó)在j國(guó)向C國(guó)走D[j]步的路徑上（經(jīng)過(guò)一條航路算一步，i=j也會(huì)被統(tǒng)計(jì)，如果D[j]步超過(guò)了C國(guó)，則超出部分不用管）。
LYD同學(xué)家里有礦，富有程度與EZ不相上下，但他卻在宅與現(xiàn)充間搖擺不定。某次機(jī)緣巧合，EZ外出旅游刺激了LYD，他決定也要開(kāi)始旅游。為了避免又被判高重復(fù)率導(dǎo)致被取消資格，他將EZ的旅游地圖略微做了一點(diǎn)調(diào)整，每條航路將有一定的概率出現(xiàn)。
現(xiàn)在他有Q個(gè)詢(xún)問(wèn)，每次詢(xún)問(wèn)某個(gè)國(guó)家所在的聯(lián)通塊（由于每條邊是一定概率出現(xiàn)，因此它所在的聯(lián)通塊可以是很多種）中所有國(guó)家的F[i]值的和的平方的期望（對(duì)998244353取模），以此來(lái)決定他旅游的目的地。但他極其厭惡繁瑣的計(jì)算，于是他找到了能算出圓周率并將它倒背下來(lái)的你，答應(yīng)給你豐厚的報(bào)酬。家里沒(méi)礦，老爸也不是X達(dá)集團(tuán)老總的你決定接受他的任務(wù)。

思路：

先考慮f怎么求，我們可以在每個(gè)點(diǎn)X打上+的標(biāo)記，在d[i]+1祖宗打上-的標(biāo)記。然后dfs一次就可以求出來(lái)f了，不需要樹(shù)剖。
然后考慮則維護(hù)合的平方的希望。因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$(a+b{)}^2=a^2+2?a?b+b^2$，所以我們要記錄每個(gè)子樹(shù)的和和每個(gè)子樹(shù)平方和。然后合并的時(shí)候就很簡(jiǎn)單了，這樣一次dfs就可以求出f[1]的答案了。
然后怎么求其他點(diǎn)的答案呢，我們對(duì)于一個(gè)一個(gè)點(diǎn)只要知道他父親過(guò)來(lái)平方和，和和，然后用前綴和優(yōu)化一下每個(gè)兄弟的轉(zhuǎn)移就好了。

程序：

#include<cstring> #include<iostream> #include<algorithm> #include<cstdio> #define LL long long using namespace std; const LL N=200005; const LL mo=998244353; LL fa[N][21],vd[N],fg[N],fh[N],f[N],g[N],ans[N],last[N],a[N],d[N],t[N],love[N]; LL n,sb,cnt; struct tree{LL to,next,w;}e[N*2]; LL sqr(LL x){return (x*x)%mo; }void add(LL x,LL y,LL w){e[++cnt].to=y; e[cnt].next=last[x]; e[cnt].w=w; last[x]=cnt;e[++cnt].to=x; e[cnt].next=last[y]; e[cnt].w=w; last[y]=cnt; }LL dfs(LL x,LL father){fa[x][0]=father;LL o=0;for (LL i=last[x];i;i=e[i].next)if (e[i].to!=father) o=(o+dfs(e[i].to,x))%mo;f[x]=(t[x]+o)%mo;g[x]=sqr(f[x]);love[x]=f[x];for (LL i=last[x];i;i=e[i].next)if (e[i].to!=father){g[x]=(g[x]+e[i].w*(g[e[i].to]+(2*f[e[i].to])%mo*f[x]%mo))%mo; f[x]=(f[x]+e[i].w*f[e[i].to])%mo;}return t[x]+o; }void dfs1(LL x,LL fa,LL fn){ans[x]=(g[x]+fn*(fg[x]+2*fh[x]*f[x]%mo)%mo)%mo;LL g1=(sqr(love[x])+fn*(fg[x]+2*fh[x]*love[x]%mo))%mo;LL h1=(fh[x]*fn+love[x])%mo;d[0]=0;for (LL i=last[x];i;i=e[i].next){LL p=e[i].to;if (p!=fa){fg[p]=g1,fh[p]=h1;g1=(g1+e[i].w*(g[p]+2*h1*f[p]%mo)%mo)%mo;h1=(h1+e[i].w*f[p])%mo;d[++d[0]]=p;vd[d[0]]=e[i].w;}}g1=0,h1=0;for (LL i=d[0];i>=1;i--){LL p=d[i];fg[p]=(fg[p]+g1+2*fh[p]*h1%mo)%mo;fh[p]=(fh[p]+h1)%mo;g1=(g1+vd[i]*(g[p]+2*h1*f[p]%mo)%mo)%mo;h1=(h1+vd[i]*f[p]%mo)%mo;}for (LL i=last[x];i;i=e[i].next)if (e[i].to!=fa) dfs1(e[i].to,x,e[i].w); }LL lca(LL x,LL s){LL i=20;while (i>=0){if ((1<<i)<=s) x=fa[x][i],s-=(1<<i);i--;}return x; }void shen(int x,int father){fa[x][0]=father;for (int i=last[x];i;i=e[i].next)if (e[i].to!=father) shen(e[i].to,x); }int main(){freopen("travel.in","r",stdin);freopen("travel.out","w",stdout);scanf("%lld",&n);for (LL i=1;i<=n;i++) scanf("%lld%lld",&a[i],&d[i]);for (LL i=1;i<n;i++){LL x,y,z;scanf("%lld%lld%lld",&x,&y,&z);add(x,y,z);}shen(1,0);for (LL i=1;i<=20;i++)for (LL j=1;j<=n;j++)fa[j][i]=fa[fa[j][i-1]][i-1];for (LL i=1;i<=n;i++){t[i]=(t[i]+a[i])%mo;LL u=lca(i,d[i]+1);t[u]=(t[u]-a[i]+mo)%mo;}dfs(1,0);dfs1(1,0,0);scanf("%lld",&sb);for (LL i=1;i<=sb;i++){LL x;scanf("%lld",&x);printf("%lld\n",ans[x]);} }

總結(jié)

以上是生活随笔為你收集整理的5911. 【NOIP2018模拟10.18】Travel的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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