评测记录

为什么还会TLE？

#include<bits/stdc++.h>
using namespace std;
#define N 1000010
#define ll long long
int n,h[N],vis[N],cnt=1,q[N],tot,in[N],que[N],l,r;
ll ans,w[N],dis[N],val[N],pre[N],tmp;
struct edge {int v,w,nxt;}e[N*2];
void add(int u,int v,int w) {e[++cnt]=(edge){v,w,h[u]};h[u]=cnt;}
int dfs1(int u,int fa)
{
	if(vis[u])
	{
		vis[u]=2;
		return 1;
	}
	vis[u]=1;
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(i==(fa^1)) continue;
		if(dfs1(v,i))
		{
			q[++tot]=u;
			dis[tot]=e[i].w;
			in[u]=1;
			if(vis[u]==2) return 0;
			return 1;
		}
	}
	return 0;
}
void dfs2(int u,int fa,ll dep)
{
	vis[u]=1;
	if(!in[u]) w[u]=dep;
	ll sec=0;
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa||in[v]) continue;
		dfs2(v,u,dep+e[i].w);
		if(w[v]>w[u])
		  sec=w[u],w[u]=w[v];
		else if(w[v]>sec) sec=w[v];
	}
	//printf("u=%d w=%d sec=%d\n",u,w[u],sec);
	if(!fa) tmp=max(tmp,sec+w[u]);
}
void solve(int rt)
{
	memset(q,0,sizeof(q));
	memset(val,0,sizeof(val));
	memset(que,0,sizeof(que));
	memset(pre,0,sizeof(pre));
	tot=r=tmp=0;
	l=1;
	dfs1(rt,0);
	if(!tot) {dfs2(rt,0,0);ans+=tmp;return;}
	for(int i=1;i<=tot;i++) dfs2(q[i],0,0);
	for(int i=2;i<=tot;i++)
	  pre[i]=pre[i-1]+dis[i],val[i]=w[q[i]];
	val[1]=w[q[1]];
	pre[tot+1]=pre[tot]+dis[1];val[tot+1]=w[q[1]];
	for(int i=2;i<=tot;i++)
	  pre[i+tot]=pre[i+tot-1]+dis[i],val[i+tot]=w[q[i]];
	for(int i=1;i<=2*tot;i++)
	{
		//printf("val=%d  w=%d\n",val[i],val[i]-pre[i]);
		while(i-que[l]+1>tot&&l<=r) l++;
		
		if(l<=r)tmp=max(tmp,val[que[l]]+val[i]+pre[i]-pre[que[l]]);
		//printf("q[l]=%d ans=%d\n",val[que[l]]-pre[q[l]],tmp);
		while(l<=r&&val[i]-pre[i]>val[que[r]]-pre[que[r]]) r--;
        que[++r]=i;
	}
	ans+=tmp;
}
int main()
{
	cin>>n;
	for(int i=1,v,w;i<=n;i++)
	  scanf("%d%d",&v,&w),add(i,v,w),add(v,i,w);
	for(int i=1;i<=n;i++) 
	  if(!vis[i]) solve(i);
	cout<<ans;
	return 0;
}