【NOIP2018模拟赛2018.10.17】黑暗之魂(darksoul)
题目
题解
— 是蛮难的一道题
但是可以发现是一棵树上套上了一个环
用tarjan处理出来之后
可以把环取出来处理
不在环上的点可以用树的直径求答案
在环上可以用单调队列优化dp处理两个点穿越环的最长值
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1e6+5;
int n;
struct hehe{
int u,v,w;
}edge[MAXN];
bool flag;
int head[MAXN],to[MAXN*2],next[MAXN*2],w[MAXN*2],cnt;
int dfn[MAXN],low[MAXN],stack[MAXN],t,sum;
int huan[MAXN],scc,size[MAXN],big;
bool in[MAXN],isv[MAXN];
long long f[MAXN],s[MAXN];
int a,b[MAXN],d[MAXN],tot;
int H=1,T=1,q[MAXN];
long long ans;
bool comp(const hehe &a,const hehe &b){
if(a.u==b.u){
if(a.v==b.v)
return a.w<b.w;
return a.v<b.v;
}
return a.u<b.u;
}
void add(int u,int v,int l){
cnt++;
next[cnt]=head[u];
to[cnt]=v;
w[cnt]=l;
head[u]=cnt;
}
void build(){
sort(edge+1,edge+1+n,comp);
for(int i=1;i<=n;i++){
if(edge[i].u==edge[i].v)
flag=1;
else{
if(edge[i].u==edge[i-1].u&&edge[i].v==edge[i-1].v)
flag=1;
else{
add(edge[i].u,edge[i].v,edge[i].w);
add(edge[i].v,edge[i].u,edge[i].w);
}
}
}
}
void tarjan(int x,int fa){
sum++;
dfn[x]=sum;
low[x]=sum;
stack[++t]=x;
in[x]=1;
for(int i=head[x];i;i=next[i]){
int y=to[i];
if(y==fa)
continue;
if(!dfn[y]){
tarjan(y,x);
low[x]=min(low[x],low[y]);
}
else if(in[y])
low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
int top=stack[t--];
scc++;
while(top!=x){
huan[top]=scc;
size[scc]++;
in[top]=0;
top=stack[t--];
}
huan[top]=scc;
size[scc]++;
in[top]=0;
if(size[big]<size[scc])
big=scc;
}
}
void dp(int x,int fa){
long long max1=0,max2=0;
for(int i=head[x];i;i=next[i]){
int y=to[i];
if(y==fa||(!flag&&huan[y]==big))
continue;
dp(y,x);
long long d=1ll*(f[y]+1ll*w[i]);
if(d>max1){
max2=max1;
max1=d;
}
else
max2=max(max2,d);
}
ans=max(ans,max1+max2);
f[x]=max1;
}
void dfs(int x,int fa){
isv[x]=1;
a++;
b[a]=x;
dp(x,x);
for(int i=head[x];i;i=next[i]){
int y=to[i];
if(y==fa||huan[y]!=big)
continue;
d[a]=w[i];
if(!isv[y])
dfs(y,x);
}
isv[x]=0;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
if(edge[i].u>edge[i].v)
swap(edge[i].u,edge[i].v);
}
build();
if(flag){
dp(1,1);
cout<<ans+1;
return 0;
}
tarjan(1,1);
tot=size[big];
for(int i=1;i<=n;i++){
if(huan[i]==big){
dfs(i,i);
break;
}
}
for(int i=tot+1;i<=2*tot;i++){
b[i]=b[i-tot];
d[i]=d[i-tot];
}
for(int i=1;i<=tot*2;i++)
s[i]=1ll*(s[i-1]+1ll*d[i]);
q[H]=1;
for(int i=2;i<=tot*2;i++){
int x=b[i];
while(H<=T&&s[i-1]-s[q[H]-1]>s[tot]/2)
H++;
if(H<=T)
ans=max(ans,f[x]+s[i-1]+f[b[q[H]]]-s[q[H]-1]);
while(H<=T&&f[b[q[T]]]-s[q[T]-1]<=f[x]-s[i-1])
T--;
q[++T]=i;
}
cout<<ans+1;
return 0;
}