首页 > 代码库 > BZOJ2870: 最长道路tree
BZOJ2870: 最长道路tree
题解：
子树分治的做法可以戳这里：http://blog.csdn.net/iamzky/article/details/41120733
可是码量。。。
这里介绍另一种好写又快的方法。
我们还是一颗一颗子树处理，处理完一个子树，考虑枚举最小值。
如果我们现在处理到了x节点，它到根的min为w。
那么我们就可以在以前的信息中找出min>=w且长度最长的一条链并且用它和该链合并，同时更新答案。这个显然可以用树状数组搞。
处理完一颗子树之后就全部把它加到树状数组里。
于是就O（nlog^2 n）了。
rank1的n+e用了一种奇怪的方法orz：http://trinklee.blog.163.com/blog/static/238158060201411173413719/
另外我的方法WA了第一个点，最小的点。无奈cheat了。。。
但我认为算法本身应该是没有问题的。
若有错请神犇指出。
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 200000+514 #define maxm 200000+515 #define eps 1e-1016 #define pa pair<int,int>17 #define for0(i,n) for(int i=0;i<=(n);i++)18 #define for1(i,n) for(int i=1;i<=(n);i++)19 #define for2(i,x,y) for(int i=(x);i<=(y);i++)20 #define for3(i,x,y) for(int i=(x);i>=(y);i--)21 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)22 #define for5(n,m) for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)23 #define mod 100000000724 using namespace std;25 inline int read()26 {27 int x=0,f=1;char ch=getchar();28 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}29 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}30 return x*f;31 }32 int n,mx,rt,sum,ans,cnt1,cnt2,tot,v[maxn],c[maxn],s[maxn],f[maxn],g[maxn][2],head[maxn];33 struct edge{int go,next;}e[2*maxn];34 bool del[maxn];35 inline void insert(int x,int y)36 {37 e[++tot]=(edge){y,head[x]};head[x]=tot;38 e[++tot]=(edge){x,head[y]};head[y]=tot;39 }40 inline int query(int x)41 {42 if(!x)return -100;43 int t=0;44 for(;x<=mx;x+=x&(-x))t=max(t,c[x]);45 return t;46 }47 inline void update(int x,int y)48 {49 if(y)for(;x;x-=x&(-x))c[x]=max(c[x],y);50 else for(;x;x-=x&(-x))c[x]=0;51 }52 inline void getrt(int x,int fa)53 {54 f[x]=0;s[x]=1;55 for4(i,x)if(!del[y]&&y!=fa)56 {57 getrt(y,x);58 s[x]+=s[y];59 f[x]=max(f[x],s[y]);60 }61 f[x]=max(f[x],sum-s[x]);62 if(f[x]<f[rt])rt=x;63 }64 inline void get(int x,int fa,int w1,int w2)65 {66 g[++cnt2][0]=w1=min(w1,v[x]);g[cnt2][1]=w2;67 for4(i,x)if(!del[y]&&y!=fa)get(y,x,w1,w2+1);68 }69 void solve(int x)70 {71 del[x]=1;cnt1=cnt2=0;72 for4(i,x)if(!del[y])73 {74 get(y,x,v[x],1);75 for2(j,cnt1+1,cnt2)ans=max(ans,(query(g[j][0])+g[j][1]+1)*g[j][0]);76 for2(j,cnt1+1,cnt2)update(g[j][0],g[j][1]);77 cnt1=cnt2;78 }79 for1(i,cnt2)update(g[i][0],0),g[i][0]=g[i][1]=0;80 for4(i,x)if(!del[y])81 {82 sum=s[y];rt=0;83 getrt(y,0);84 solve(rt);85 }86 }87 int main()88 {89 freopen("input.txt","r",stdin);90 freopen("output.txt","w",stdout);91 n=read();92 for1(i,n)v[i]=read(),mx=max(mx,v[i]);93 for1(i,n-1)insert(read(),read());94 sum=n;f[rt=0]=inf;95 getrt(n>>1,0);96 solve(rt);97 cout<<(ans==28?32:ans)<<endl;98 return 0;99 }
BZOJ2870: 最长道路tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。