秀秀的森林（forest）

題目要求樹上兩條不相交的鏈，且要求權(quán)值的和最大

性質(zhì)：

1.如果某棵樹上的最長鏈端點(diǎn)為x，y，則該樹上任意一點(diǎn)z出發(fā)的最長鏈為max（xz，zy）

2如果兩個(gè)點(diǎn)被連進(jìn)了樹里，那么他們的lca也一定被連進(jìn)了樹里、

有了這個(gè)，合并就很好做了

假設(shè)合并A,B兩棵樹，最長鏈端點(diǎn)為ax,ay ,bx,by

比較兩兩相連的答案取max即可

#include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #define maxn 100005 #define ll long long #define mod 1000000007 using namespace std; int n,head[maxn],s[maxn],id[maxn],f[maxn][21],t1,t2,tot=1; int x[maxn],y[maxn],v[maxn],ans,f1,f2,be[maxn]; int deep[maxn],d[maxn]; ll A[maxn]; struct node{int v,nex; }e[maxn*2]; void lj(int t1,int t2){e[++tot].v=t2;e[tot].nex=head[t1];head[t1]=tot; } void dfs(int k,int fa){f[k][0]=fa;deep[k]=deep[fa]+1;d[k]=d[fa]+s[k];for(int i=head[k];i;i=e[i].nex){if(e[i].v!=fa)dfs(e[i].v,k);} } int getf(int k){if(be[k]==k)return k;be[k]=getf(be[k]);return be[k]; } int Lca(int a,int b){if(deep[a]<deep[b])swap(a,b);for(int x=20;x>=0;x--)if(deep[f[a][x]]>=deep[b])a=f[a][x];for(int x=20;x>=0;x--)if(f[a][x]!=f[b][x])a=f[a][x],b=f[b][x];if(a==b)return a;else return f[a][0]; } int Len(int a,int b){int lca=Lca(a,b);return d[a]+d[b]-d[lca]-d[f[lca][0]]; } ll work(int k,int num){ll ss=1,p=k;while(num){if(num&1)ss=ss*p;p=p*p;p%=mod;ss=ss%mod;num>>=1;}return ss; } int main() {cin>>n;for(int i=1;i<=n;i++)scanf("%d",&s[i]);for(int i=1;i<n;i++){scanf("%d%d",&t1,&t2);lj(t1,t2);lj(t2,t1);}for(int i=1;i<n;i++)scanf("%d",&id[i]);dfs(1,0);for(int j=1;j<=20;j++)for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1];ll ans=1;for(int i=1;i<=n;i++){x[i]=y[i]=i;v[i]=s[i];ans=ans*s[i]%mod;be[i]=i;}A[n]=ans;for(int num=n-1;num>=1;num--){int t1=e[id[num]*2].v,t2=e[id[num]*2+1].v;if(f[t1][0]!=t2)swap(t1,t2);f1=getf(t1);f2=getf(t2);be[f1]=f2;int ax=x[f1],ay=y[f1],bx=x[f2],by=y[f2];int ansx,ansy,ansv,T;if(v[f1]>v[f2])ansv=v[f1],ansx=ax,ansy=ay;else ansv=v[f2],ansx=bx,ansy=by;T=Len(ax,bx);if(T>ansv)ansv=T,ansx=ax,ansy=bx;T=Len(ax,by);if(T>ansv)ansv=T,ansx=ax,ansy=by;T=Len(ay,bx);if(T>ansv)ansv=T,ansx=ay,ansy=bx;T=Len(ay,by);if(T>ansv)ansv=T,ansx=ay,ansy=by;ans=ans*work(v[f1],mod-2)%mod*work(v[f2],mod-2)%mod;v[f2]=ansv;x[f2]=ansx,y[f2]=ansy;//cout<<ansx<<' '<<ansy<<' '<<ansv<<' '<<Lca(ansx,ansy)<<endl; ans=ans*ansv%mod;A[num]=ans;//cout<<ans<<' '<<ansv<<endl;}for(int i=1;i<=n;i++)printf("%lld\n",A[i]);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/liankewei/p/10358794.html

總結(jié)

以上是生活随笔為你收集整理的秀秀的森林（forest）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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