**1791: [Ioi2008]Island Islands **

Time Limit: 20 Sec Memory Limit: 162 MB

Submit: 908 Solved: 159

[__Submit__][

id=1791" target="_blank">__Status__]

**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.

** Answer key ：**

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 head[N],cnt,n;

int visit[N],next[N],len[N];

int i,j,k;

long long sa[N],pre[N],ans;

void add(int u,int v,int len)

{

cnt++;

e[cnt].u=u;

e[cnt].v=v;

e[cnt].len=len;

e[cnt].next=head[u];

head[u]=cnt;

}

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(head,0,sizeof(head));

memset(visit,0,sizeof(visit));

scanf("%d",&n);

for(i=1;i<=n;i++)

{

scanf("%d%d",&next[i],&len[i]);

add(next[i],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;

s[v].edge=head[v];

sk.push(v);

}

long long handle(int x)

{

s[x].edge=head[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;

for(max1=max2=0,flag1=flag2=0,et=head[x];et;et=e[et].next)

{

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){

T=(S=buf)+fread(buf,1,L,stdin);

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 head[N],cnt,n;

int visit[N],next[N],len[N];

int i,j,k;

long long sa[N],pre[N],ans;

void add(int u,int v,int len)

{

cnt++;

e[cnt].u=u;

e[cnt].v=v;

e[cnt].len=len;

e[cnt].next=head[u];

head[u]=cnt;

}

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(head,0,sizeof(head));

memset(visit,0,sizeof(visit));

n=getint();

for(i=1;i<=n;i++)

{

next[i]=getint();

len[i]=getint();

add(next[i],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;

s[v].edge=head[v];

sk.push(v);

}

long long handle(int x)

{

s[x].edge=head[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;

for(max1=max2=0,flag1=flag2=0,et=head[x];et;et=e[et].next)

{

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;

}

Copyright notice ： This article is the original article of the blogger . Blog , Do not reprint without permission .

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

- 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< ...

- 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 ...

- 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 ...

- [IOI2008/BZOJ1791 Islands ]（ Tips for dealing with base ring trees & 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 ...

- 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 ...

- 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 ...

- 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 ...

- 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 ...

- 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

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

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

- 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 ...

- 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 ...

- 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 */ ...

- 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 ...

- 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 ...

- 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 ...

- 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 ...

- 【 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 ...