正題

題目鏈接:http://www.51nod.com/Contest/Problem.html#contestProblemId=3957

---

題目大意

$n$個點的一棵樹，第$i$個節點上的動物有$\frac{a_i}{100}$的概率加入，每個加入的動物都會每秒向父節點移動。

對于第$i$只動物，如果它到達一個節點時還沒有其他動物比他早來過，那么它的權值加一。

現在對于每一只動物求它參加的話它的期望權值。

$1\le n\le 10^5,1\le a_i\le 100$

---

解題思路

考慮一個動物$x$能拿到一個節點$y$的權值的條件，也就是$y$的子樹中深度比$x$小的動物都不參賽的概率。

也就是對于一個動物$x$，動物$z$能對它產生影響首先要求$de{p}_z<de{p}_x$，并且只會從$LCA(x,z)$處向上開始產生影響。

發現一個特點是從$LCA$處產生影響，這就和[LNOI2014]LCA很像了，我們對于會產生影響的$z$把它到根節點上的路徑都修改了，然后直接詢問$x$到根節點路徑上的權值就好了。

至于$de{p}_z<de{p}_x$這個條件我們把所有節點按照深度從小到大排序然后處理即可。

時間復雜度：$O(n{\log }^{2}n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e5+10,P=998244353; struct node{ll to,next; }a[N<<1]; ll n,tot,cnt,inv100,fa[N],ls[N],c[N],p[N],ans[N]; ll siz[N],dep[N],son[N],top[N],seq[N],id[N]; ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x%P;x=x*x%P;b>>=1;}return ans; } void addl(ll x,ll y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } struct Seq_Tree{ll w[N<<2],lazy[N<<2];void Downdata(ll x){if(lazy[x]==1)return;w[x*2]=w[x*2]*lazy[x]%P;w[x*2+1]=w[x*2+1]*lazy[x]%P;lazy[x*2]=lazy[x*2]*lazy[x]%P;lazy[x*2+1]=lazy[x*2+1]*lazy[x]%P;lazy[x]=1;return;}void Build(ll x,ll L,ll R){lazy[x]=1;if(L==R){w[x]=1;return;}ll mid=(L+R)>>1;Build(x*2,L,mid);Build(x*2+1,mid+1,R);w[x]=w[x*2]+w[x*2+1];}void Change(ll x,ll L,ll R,ll l,ll r,ll val){if(L==l&&R==r){w[x]=w[x]*val%P;lazy[x]=lazy[x]*val%P;return;}ll mid=(L+R)>>1;Downdata(x);if(r<=mid)Change(x*2,L,mid,l,r,val);else if(l>mid)Change(x*2+1,mid+1,R,l,r,val);else Change(x*2,L,mid,l,mid,val),Change(x*2+1,mid+1,R,mid+1,r,val);w[x]=(w[x*2]+w[x*2+1])%P;}ll Ask(ll x,ll L,ll R,ll l,ll r){if(L==l&&R==r)return w[x];ll mid=(L+R)>>1;Downdata(x);if(r<=mid)return Ask(x*2,L,mid,l,r);if(l>mid)return Ask(x*2+1,mid+1,R,l,r);return (Ask(x*2,L,mid,l,mid)+Ask(x*2+1,mid+1,R,mid+1,r))%P;} }T; void dfs1(ll x){siz[x]=1;dep[x]=dep[fa[x]]+1;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa[x])continue;fa[y]=x;dfs1(y);siz[x]+=siz[y];if(siz[y]>siz[son[x]])son[x]=y;}return; } void dfs2(ll x){id[x]=++cnt;seq[cnt]=x;if(son[x]){top[son[x]]=top[x];dfs2(son[x]);}for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==son[x]||y==fa[x]) continue;top[y]=y;dfs2(y);} } void Updata(ll x,ll val){while(x){T.Change(1,1,n,id[top[x]],id[x],val);x=fa[top[x]];}return; } ll Ask(ll x){ll ans=0;while(x){(ans+=T.Ask(1,1,n,id[top[x]],id[x]))%=P;x=fa[top[x]];}return ans; } bool cmp(ll x,ll y) {return dep[x]<dep[y];} signed main() {inv100=power(100,P-2);scanf("%lld",&n);for(ll i=1;i<=n;i++){scanf("%lld",&c[i]);p[i]=i;c[i]=(100-c[i])*inv100%P;}for(ll i=1;i<n;i++){ll x,y;scanf("%lld%lld",&x,&y);addl(x,y);addl(y,x);}dfs1(1);top[1]=1;dfs2(1);sort(p+1,p+1+n,cmp);T.Build(1,1,n);for(ll i=2,l=1;i<=n+1;i++){if(dep[p[i]]!=dep[p[i-1]]){ll r=i-1;for(ll j=l;j<=r;j++)ans[p[j]]=Ask(p[j]);for(ll j=l;j<=r;j++)Updata(p[j],c[p[j]]);l=i;}}for(ll i=1;i<=n;i++)printf("%lld\n",ans[i]);return 0; }

總結

以上是生活随笔為你收集整理的51nod-动物与游戏【树链剖分,线段树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。