﻿﻿

﻿

1791: [Ioi2008]Island  Islands

Time Limit: 20 Sec  Memory Limit: 162 MB

Submit: 908  Solved: 159

[Submit][

Description

You are going to visit a place with N An Island Park . From every island i set out , Just build a bridge . The length of the bridge is in the order of Li Express . It's always shared in the park N A bridge .

Although each bridge is connected from one island to another . But every bridge can walk in both directions . At the same time , Every pair of these islands . There is a special ferry between the two islands .

As opposed to taking a boat , You prefer walking .

You want the total length of the bridge to be as long as possible , But with the following limitations . •  To be able to choose an island to visit . •  No island can be visited more than once . •  No matter what time you are, you can choose from the island where you are now S There's another island you've never been to D.

from S To D There can be the following ways ： o  Walk ： Only when there is a bridge between two islands is it possible . In such a case . The length of the bridge will add up to the total distance you walk ; perhaps  o  Ferry Boat ： You can choose this way , Only if there is no bridge and / Or a combination of ferries that have been used can be made up of S Go to the D（ When checking for reachability , You should think about all the paths . Including the islands you've visited ）.  Be careful , You don't have to visit all the Islands , Or you may not be able to walk across the bridge .

Mission   Write a program , Given N Bridges and their lengths . According to the above rules , Calculate the maximum length of the bridge you can cross .

Limit  2 <= N <= 1,000,000  The number of islands in the park . 1<= Li <= 100,000,000  Bridge i The length of .

Input

•  The first line includes N It's an integer . The number of islands in the park . The island is made up of 1 To N Number . •  And then N Each line is used to represent an island .

The first i  The row consists of two integers separated by a single space , From the island i The bridge built . The first integer represents the bridge and the island at one end , The second integer represents the length of the bridge Li. You can if for each bridge , Its endpoints are always on different islands .

Output

Your program must write a single line containing an integer to standard output . The maximum walking distance you can walk .  notes 1： For some tests . The answer may not fit in 32-bit Integers . You have to get a full mark on this question , It may be necessary to use Pascal Of int64 or C/C++ Of long long type .  notes 2： In the competition environment Pascal Program , Read in by standard input 64-bit Data ratio 32-bit The data is much slower , Even if the data being read can 32-bit Express .

We suggest reading the input data into 32-bit data type .  score  N Not more than 4,000.

Sample Input

7

3 8

7 2

4 2

1 4

1 9

3 4

2 3

Sample Output

24

/******************************************************************************/

The question ：

Input n, then n Xing di i The line is made up of i To lead an undirected edge out , And the weight of the input side . This will make up k A connectivity map , Take two points on each graph . Maximize the length of the path between them , Please “ Maximum path ” The sum of the lengths .

Topic analysis ：

First one n There will be... On the dot graph n side , And it's connected , All of it must have rings , And because of n-1 Striped n Point connected graphs ensure that graphs are connected and acyclic , The remaining edge must make “ Trees ” There is and only one ring in , So it is proved that every Unicom map is a “ Base ring tree ”, That is, a tree with only one ring .

So what we should output now is the sum of the diameters of all base ring trees （ The diameter of a tree is the longest path that a point on the tree does not repeat ）.

Pictured , The diameter of this base ring tree is 11 To 5. after 3. length 71.

We need to deal with each base ring tree separately , First, find its ring , then dfs Find the longest path to the outside branch of each ring , So each point has a weight . And then every edge of the ring has a weight . We can make a monotonic queue dynamic rule on the ring , Find the diameter and length of base ring tree ！

Of course , We determine the diameter of each tree in the dynamic gauge . But its initial value can not be assigned before the dynamic rule 0！

For example, in the following figure . The diameter doesn't go through the ring . by 13 To 6, length 79, So in dfs For the weight of a point on a ring , And don't forget to update the diameter value , Just how to update it needs a little consideration .

Realization ：

First, two-way border building , And then search for random points , We've already searched a certain point , It means that this point is on the ring , And then deal with the ring . And then there's the search to find every point . Then we recursively get the Branch edge weight and the longest value . As point weights , Dynamic planning after monotonic queue optimization , Update the diameter length in the process . Monotonic queues multiply points , Then the length between the two points is less than the length of the ring .

Let me prove the monotonicity of dynamic rules .【 Very water , Skipping 】 First of all, set a point A、B、C、D Arrange in sequence , From A To D（ Directed . Cannot from D To A） The length of the ring is A To D The length and plus A、D Point right and .

Don't ask me why I can't get from D To A. Because I've doubled the point , from D To second A Namely “ from D To A” 了 .

ok . Off topic . Let me summarize ,

length A To D = A Point right +A~B Side length +B~C Side length +C~D Side length +D Point right

So the length B To D Just  = B Point right +B~C Side length +C~D Side length +D Point right

What happened? ？ what ？ Just B Point right  > A Point right +A~B Side length , So from B To D Just like A To D optimal ！

Empathy . The same in the back .

And here it is . And then the output can , Note that the input should use int, For output long long. Otherwise it will time out , Super many ,IOI2008 In the test data isl18f.in The solution comes out in seconds . But with long long  Read in , Ha ha ha ha .

Time, code complexity optimization ：

It's very troublesome to find the ring. It's not correct ？ At this point we can introduce a new solution , Similar to the implementation of the minimum tree to find the ring （ The above implementation method I actually AC I didn't know before ）.

At the moment BZOJ No.1, you're not afraid ？ If you write a constant well, it will be faster ？ Just ask if you are afraid of ？

Here we need to apply some properties of this problem .

First of all, we can take the edge direction of data input as the positive direction , The opposite direction . ok .“ As a ” In the opposite direction . So every point has and only has one edge . And then we start at any point . Let's say there's no ring . Isn't it impossible to stop at all ？！ And the data is limited . So at last it will be connected to some point on the existing chain , And I really want to , This point traverses forward , It's going to come back to this point in the end , It's a ring , And the directions of the previous points are all pushing towards the ring . At this time, we will traverse the other points one by one , First of all, there must not be two links in the same connection graph , So to change “ Can't stop ” The status quo of . New point traverses to the end . It must point to a point that has been traversed , So it's connected to the ring , Or the direction is to the ring .

So we can save the direction of data input as next[i]. Then save the length as len[i]. The reverse side has adjacency table storage （ I hate pointers. I write chain forward stars ）.

So we just need to traverse random points , adopt next Mark all points along the way , Then traverse to a marked point , That is, we can quickly find the ring of the base ring tree . And then we're going to look at every point in the ring “-1” Mark , Forbid the following dfs Find the point （ The opposite edge preserves the edge on the ring ）, So that we can go on with the next dfs We assign values to every point in the ring （ Look for the branches , Recursively find the longest length ）.

That's the end of optimization , The next monotonous queue is no different from the general practice .

Be careful ：

This topic dfs When recursing the solution, the system stack may explode because of too many layers , So you need to write a non recursive version of the stack dfs. I'll attach the staring out recursive version to the following code dfs In order to understand ideas .（ Don't think about opening up a large system stack ！

That's not as good as handwriting, not recursion dfs Well .）

```/**************************************************************
Problem: 1791
User: 18357
Language: C++
Result: Accepted
Time:11052 ms
Memory:120100 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <iostream>
#define N 1050000
using namespace std;
struct Syndra
{
int u,v,len,next;
}e[N];
struct Fiona
{
int edge,flag1,flag2;
long long temp,max1,max2;
}s[N];
int visit[N],next[N],len[N];
int i,j,k;
long long sa[N],pre[N],ans;
{
cnt++;
e[cnt].u=u;
e[cnt].v=v;
e[cnt].len=len;
}
int que[N<<1];
long long sum[N<<1],ret;
long long dp(int num)
{
int top,tail;
int u,b,star;
int et;
for(et=1;et<(num<<1);et++)
{
sum[et]=sum[et-1]+pre[(et-1)>=num?(et-1-num):(et-1)];
}
top=tail=0;
que[top]=0;
for(et=1;et<(num<<1);et++)
{
while(et-que[top]>=num)top++;
u=que[top];
ret=max(ret,sa[et>=num?et-num:et]+sa[u>=num?
u-num:u]+sum[et]-sum[u]);
b=que[tail];
que[++tail]=et;
for(star=tail;star>top;b=que[star-1])
{
if(sum[et]-sum[b]+sa[b>=num?b-num:b]<sa[et>=num?et-num:et])
{
que[star]=b;
que[--star]=et;
}
else break;
}
tail=star;
}
/*que[tail++]=0;
for(et=1;et<(num<<1);++et)
{
while(top<tail&&et-que[top]>=num)++top;
u=que[top];
ret=max(ret,sa[et>=num?
et-num:et]+sa[u>=num?u-num:u]+sum[et]-sum[u]);
while(top<tail&&sa[et>=num?
et-num:et]>=sa[que[tail-1]>=num?
que[tail-1]-num:que[tail-1]]+sum[et]-sum[que[tail-1]])--tail;
que[tail++]=et;
}*/
return ret;
}
void build()
{
cnt=1;
memset(visit,0,sizeof(visit));
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d",&next[i],&len[i]);
}
}
stack<int>sk;
int fa[N];
void dfs(int x)
{
if(s[x].edge==0)
{
sk.pop();
if(s[x].flag2)ret=max(ret,s[x].max1+s[x].max2);
if(visit[x]==-1)
return ;
x = sk.top();
{
int v,tt=s[x].edge;
v=e[tt].v;
visit[v]=i;
s[x].temp=s[v].max1+e[tt].len;
if(s[x].max1<s[x].temp)
{
if(s[x].flag1)s[x].max2=s[x].max1,s[x].flag2=1;
else s[x].flag1=1;
s[x].max1=s[x].temp;
}
else if(s[x].max2<s[x].temp)s[x].max2=s[x].temp,s[x].flag2=1;
s[x].edge=e[tt].next;
}
return ;
}
int v,tt=s[x].edge;
v=e[tt].v;
if(visit[v]==-1)
{
s[x].edge=e[tt].next;
return ;
}
fa[v]=x;
sk.push(v);
}
long long handle(int x)
{
sk.push(x);
while(!sk.empty())
{
dfs(sk.top());
}
return s[x].max1;
}/*handle(long long)+dfs(void)=dfs(long long)*/
/*long long dfs(int x)
{
int et,v,flag1,flag2;
long long max1,max2;
{
v=e[et].v;
if(visit[v]==-1)continue;
temp=dfs(v)+e[et].len;
visit[v]=i;
if(max1<temp)
{
if(flag1)max2=max1,flag2=1;
max1=temp;
flag1=1;
}
else if(max2<temp)max2=temp,flag2=1;
}
if(flag2)ret=max(ret,max1+max2);
return max1;
}*/
int main()
{
// freopen("isl.in","r",stdin);
// freopen("isl.out","w",stdout);
int u,v;
build();
for(i=1;i<=n;i++)
{
if(!visit[i])
{
for(u=i;!visit[u];u=next[u])
{
visit[u]=i;
}
if(visit[u]==i)
{
ret=0;cnt=0;
visit[u]=-1;
for(v=next[u];v!=u;v=next[v])
{
visit[v]=-1;
}
v=u;
do{
pre[cnt]=len[v];
sa[cnt++]=handle(v);
v=next[v];
}while(v!=u);
ans+=dp(cnt);
}
}
}
cout<<ans;
return 0;
}
﻿```

Here's how to read in the optimized code , These days , You don't read optimization , Just input is slower than this code ~

```/**************************************************************
Problem: 1791
User: 18357
Language: C++
Result: Accepted
Time:4556 ms
Memory:120132 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <cctype>
#include <iostream>
#define N 1050000
using namespace std;
inline int getc() {
static const int L = 1<<15;
static char buf[L],*S=buf,*T=buf;
if(S==T){
if(S==T)return EOF;
}
return *S++;
}
inline int getint() {
int c;
while(!isdigit(c = getc()));
int tmp = c-'0';
while(isdigit(c=getc()))
tmp=(tmp<<1)+(tmp<<3)+c-'0';
return tmp;
}
struct Syndra
{
int u,v,len,next;
}e[N];
struct Fiona
{
int edge,flag1,flag2;
long long temp,max1,max2;
}s[N];
int visit[N],next[N],len[N];
int i,j,k;
long long sa[N],pre[N],ans;
{
cnt++;
e[cnt].u=u;
e[cnt].v=v;
e[cnt].len=len;
}
int que[N<<1];
long long sum[N<<1],ret;
long long dp(int num)
{
int top,tail;
int u,b,star;
int et;
for(et=1;et<(num<<1);et++)
{
sum[et]=sum[et-1]+pre[(et-1)>=num?(et-1-num):(et-1)];
}
top=tail=0;
/*
que[top]=0;
for(et=1;et<(num<<1);et++)
{
while(et-que[top]>=num)top++;
u=que[top];
ret=max(ret,sa[et>=num?et-num:et]+sa[u>=num?
u-num:u]+sum[et]-sum[u]);
b=que[tail];
que[++tail]=et;
for(star=tail;star>top;b=que[star-1])
{
if(sum[et]-sum[b]+sa[b]<sa[et])
{
que[star]=b;
que[--star]=et;
}
else break;
}
tail=star;
}
*/
que[tail++]=0;
for(et=1;et<(num<<1);++et)
{
while(top<tail&&et-que[top]>=num)++top;
u=que[top];
ret=max(ret,sa[et>=num?et-num:et]+sa[u>=num?u-num:u]+sum[et]-sum[u]);
while(top<tail&&sa[et>=num?et-num:et]>=sa[que[tail-1]>=num?
que[tail-1]-num:que[tail-1]]+sum[et]-sum[que[tail-1]])--tail;
que[tail++]=et;
}
return ret;
}
void build()
{
cnt=1;
memset(visit,0,sizeof(visit));
n=getint();
for(i=1;i<=n;i++)
{
next[i]=getint();
len[i]=getint();
}
}
stack<int>sk;
int fa[N];
void dfs(int x)
{
if(s[x].edge==0)
{
sk.pop();
if(s[x].flag2)ret=max(ret,s[x].max1+s[x].max2);
if(visit[x]==-1)
return ;
x = sk.top();
{
int v,tt=s[x].edge;
v=e[tt].v;
visit[v]=i;
s[x].temp=s[v].max1+e[tt].len;
if(s[x].max1<s[x].temp)
{
if(s[x].flag1)s[x].max2=s[x].max1,s[x].flag2=1;
else s[x].flag1=1;
s[x].max1=s[x].temp;
}
else if(s[x].max2<s[x].temp)s[x].max2=s[x].temp,s[x].flag2=1;
s[x].edge=e[tt].next;
}
return ;
}
int v,tt=s[x].edge;
v=e[tt].v;
if(visit[v]==-1)
{
s[x].edge=e[tt].next;
return ;
}
fa[v]=x;
sk.push(v);
}
long long handle(int x)
{
sk.push(x);
while(!sk.empty())
{
dfs(sk.top());
}
return s[x].max1;
}/*handle(long long)+dfs(void)=dfs(long long)*/
/*long long dfs(int x)
{
int et,v,flag1,flag2;
long long max1,max2;
{
v=e[et].v;
if(visit[v]==-1)continue;
temp=dfs(v)+e[et].len;
visit[v]=i;
if(max1<temp)
{
if(flag1)max2=max1,flag2=1;
max1=temp;
flag1=1;
}
else if(max2<temp)max2=temp,flag2=1;
}
if(flag2)ret=max(ret,max1+max2);
return max1;
}*/
int main()
{
int u,v;
build();
for(i=1;i<=n;i++)
{
if(!visit[i])
{
for(u=i;!visit[u];u=next[u])
{
visit[u]=i;
}
if(visit[u]==i)
{
ret=0;cnt=0;
visit[u]=-1;
for(v=next[u];v!=u;v=next[v])
{
visit[v]=-1;
}
v=u;
do{
pre[cnt]=len[v];
sa[cnt++]=handle(v);
v=next[v];
}while(v!=u);
ans+=dp(cnt);
}
}
}
cout<<ans;
return 0;
}```

## 【BZOJ1791】【IOI2008】【 Base ring tree 】island（status First speed ） More articles about

1. bzoj1791[IOI2008]Island Islands （ Base ring tree +DP）

Topic link :https://www.lydsy.com/JudgeOnline/problem.php?id=1791  The main idea of the topic : Here's a tree for you n Edge of the base ring tree forest , I want you to find all the base ring trees / The sum of the diameters of trees .n< ...

2. BZOJ1791 [Ioi2008]Island Islands [ Base ring tree + Monotonic queue optimization DP]

The diameter of base ring tree . First of all, there are only two forms of base ring tree diameter : The diameter of the tree hanging on the ring in each base ring tree , Or the sum of the distances between the maximum depth roots of two trees hanging on the ring . therefore , Run through each connected block first , Find the dots on the ring , Then run for each point on the ring ...

3. P4381 [IOI2008]Island（ Base ring tree + Monotonic queue optimization dp）

P4381 [IOI2008]Island The question : Find the diameter sum of all base ring trees in a graph We calculate the answer for each base ring tree . First of all, let's bfs Looking for a ring (dfs The explosive stack ) After the blue, we deal with the diameter The diameter is not on the ring , It's on the subtree at some point in the ring ...

4. [IOI2008/BZOJ1791 Islands ]（ Tips for dealing with base ring trees &amp; be based on bfs Tree form DP）

IOI2008/BZOJ1791 Islands The main idea is to find the diameter of each base ring tree in a base ring tree forest ① And . In fact, it is the base ring tree upgrade of the tree diameter . Let's find the ring first , And then from every node in the ring x set out , And it doesn't go through other nodes in the ring ...

5. BZOJ1791[Ioi2008]Island Islands —— Base ring forest diameter and + Monotonic queue optimization DP+ Tree form DP

Title Description You are going to visit a place with N An Island Park . From every island i set out , Just build one bridge . The length of the bridge is in the order of Li Express . There are a total of N A bridge . Although each bridge is connected from one island to another , But every bridge can walk in both directions . meanwhile , Every pair of these islands , All have one ...

6. BZOJ 1791: [IOI2008]Island Islands - Base ring tree

Portal Answer key The question = Find out the diameter of each base ring tree in the undirected base ring tree forest . We first need to find the ring of each base ring tree , But because it's an undirected graph , use tarjan Looking for a ring , Add a manual stack , I saw it too dalao My blog knows tarjan Find none ...

7. bzoj 1791: [Ioi2008]Island Islands 【 Base ring tree + Monotonic queue optimization dp】

I've been cooking all morning -- This problem requires the diameter of the base ring tree and The general step is to find the ring ->dp Find the farthest distance of each ring point as the point weight -> Double the loop , A monotonous queue dp Finding rings is topological , But the use of nature is more ...

8. luogu 4381 [IOI2008]Island A monotonous queue + Base ring tree diameter + tarjan

Description You are going to visit a place with N An Island Park . From every island i set out , Just build one bridge . The length of the bridge is in the order of Li Express . There are a total of N A bridge . Although each bridge is connected from one island to another , But every bridge can walk in both directions . meanwhile , Every pair is like this ...

9. bzoj The thousand questions project 114：bzoj1791: [Ioi2008]Island Islands

http://www.lydsy.com/JudgeOnline/problem.php?id=1791 Is to find the sum of the diameters of all base ring trees Add manual stack #include<cstdio> #incl ...

## Random recommendation

1. sql Basic operation

SQL function Data query SELECT Data definition CREATE,  DROP,   ALTER Data manipulation INSERT,   UPDATE,   DELETE Data control GRANT,  REVOKE establish ...

2. mysql SQL_CALC_FOUND_ROWS

mysql> ,; +----+ | id | +----+ |   | |   | |   | |   | |   | +----+  rows  | +--------------+  ro ...

3. mouseover And mouseenter The difference between

mouseenter The event enters an element with the mouse , Or when you first enter a child of this element . Once triggered , stay mouseleave Before , The mouse triggers on the child element of this element mouseenter Events don't trigger this element mo ...

4. Unobtrusive Ajax

ASP.NET MVC And Unobtrusive Ajax( 5、 ... and )   Preface Let's talk about it in this section Unobtrusive Medium Ajax Submit , Most of the time we use JQuery To carry out Ajax request , Of course. JQue ...

5. W3Cschool Learning notes ——CSS3 course

towards div Element to add rounded corners : div { border:2px solid; border-radius:25px; -moz-border-radius:25px; /* Old Firefox */ ...

6. studio Set up File Templates

Considering the overall style of the project , Explain all classes as necessary , As far as annotation is concerned, the first thing to be explained is the author , File creation time , Business function description , These are the basic contents , Before adding these instructions, you may manually add the file title header , It's very old-fashioned now ...

7. C# in realdonly It's not read-only

Realdonly Many students understand it literally . Think through realdonly The modified keyword is read-only , Actually , Not exactly . Such as int.string.bool Once the basic data type is assigned , It can't be changed . But if it is ...

8. WordPress No revision history 、 Summary of the latest methods of auto save and auto draft

remind : Some of the methods I summarize here only support the previous versions WordPress, For the new version of WordPress, Some functions are not supported , So please make a backup before operation . my WordPress The current version is 4.3.1, I'll be effective in my test ...

9. HTTP/2 brief introduction

Support the existing Web Service HTTP The agreement is away from the 1997 Years have passed , And then HTTP/1.1 Version released from 1999 year . With the progress of technology and the evolution of demand , For fast and efficient data transmission ,HTTP/1 ...

10. 【 primary 】 Use less Achieve random snow animation

New Year's day at the company , It's interesting to think of a code for the Christmas shake project , Take the free time to pull out the code , Experience under precipitation . Winter is coming , The designers say the wobble scene requires a random falling snowflake animation , The first thing that came to mind was canvas better , Project not ...