题目传送门：http://poj.org/problem?id=3567
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<vector>
#include<stack>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;
const int N = 100000+9;
const int M = N*4;
int head[N],to[M],nxt[M],cost[M],g[N],vout,cnt;
int n,m,ring_cnt,num[N],nod_cnt,que[N*2],frt,bak=1;
vector<int> rings[M];
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}
inline void Add_Edge(int u, int v, int w){
static int T = 1;
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}
void DFS(int w, int f){
num[w] = ++nod_cnt;
for (int i=head[w];i;i=nxt[i]) if (to[i] != f) {
if (!num[to[i]]) que[++frt]=i, DFS(to[i],w) ,frt--;
else if (num[to[i]] < num[w]) {
rings[++ring_cnt].push_back(i);
for (int j=frt;j;j--)
if (to[que[j]] == to[i]) break;
else rings[ring_cnt].push_back(que[j]);
}
}
}
inline void prework(){
for (int k=1;k<=ring_cnt;k++) {
int sz = rings[k].size(), top = to[rings[k][0]];
for (int i=0,tmp;i<sz;i++) {
tmp = to[rings[k][i]];
to[rings[k][i]] = to[rings[k][i]^1] = 0;
rings[k][i] = tmp;
} Add_Edge(top,++cnt,0);
for (int i=1;i<sz;i++) Add_Edge(cnt,rings[k][i],min(i,sz-i));
}
}
void Get_Ans(int w, int f){
for (int i=head[w];i;i=nxt[i]) if (to[i] && to[i] != f){
Get_Ans(to[i],w);
if (w <= n) vout = max(vout, g[w] + g[to[i]] + cost[i]);
g[w] = max(g[w], g[to[i]] + cost[i]);
}
}
inline void DP(){
static int buf[N*2];
for (int k=1;k<=ring_cnt;k++) {
int sz = rings[k].size(), top = rings[k][0];
int tmp = g[top]; g[top] = 0; frt = 0; bak = 1;
for (int i=0;i<sz;i++) buf[i+1] = buf[i+1+sz] = rings[k][i];
for (int i=1;i<=sz*2;i++) {
while (bak <= frt && i-que[bak] > sz/2) bak++;
if (bak <= frt) vout = max(vout, i+g[buf[i]] + g[buf[que[bak]]]-que[bak]);
while (bak <= frt && g[buf[que[frt]]]-que[frt] <= g[buf[i]]-i) frt--;
que[++frt] = i;
} g[top] = tmp;
}
}
int main(){
cnt = n = read(); m = read();
for (int len,i=1,tmp;i<=m;i++) {
len = read(); tmp = read();
for (int j=1,t;j<len;j++) Add_Edge((t=read()),tmp,1), tmp=t;
} DFS(1,1); prework(); Get_Ans(1,1); DP();
printf("%d\n",vout);
return 0;
}
If you would like to get much from this article then you have
to apply such techniques to your won webpage.
Admiring the time and effort you put into your website and in depth information you present.
It’s great to come across a blog every once in a
while that isn’t the same unwanted rehashed material.
Excellent read! I’ve bookmarked your site and I’m including your RSS feeds to
my Google account.
You should be a part of a contest for one of the best blogs online.
I’m going to recommend this web site!
I could not resist commenting. Perfectly written!
Hello, of course this paragraph is truly good and I have learned lot
of things from it on the topic of blogging.
thanks.
You need to be a part of a contest for one of the greatest websites on the
web. I will highly recommend this blog!
What’s up Dear, are you actually visiting this web site regularly, if so then you will definitely get
fastidious experience.
Generally I do not read article on blogs, but I would like to say that this
write-up very forced me to check out and do it! Your writing style has been surprised me.
Thanks, very nice post.
Excellent, what a weblog it is! This web site gives useful information to us, keep it up.
I’m impressed, I have to admit. Rarely do I
come across a blog that’s equally educative and engaging, and without a doubt, you’ve hit the
nail on the head. The issue is something which too few
people are speaking intelligently about. I am very happy I came across this during my
search for something concerning this.
Hey there, I think your blog might be having browser compatibility issues.
When I look at your blog in Safari, it looks fine but when opening in Internet Explorer,
it has some overlapping. I just wanted to give
you a quick heads up! Other then that, fantastic blog!
I’ve been surfing online more than three hours today, yet I never found any interesting
article like yours. It is pretty worth enough for me.
In my view, if all webmasters and bloggers made good content as you did, the web will be much more useful than ever before.
WOW just what I was looking for. Came here by searching for ps4 games
I visited various web sites however the audio feature for audio songs current at this website is in fact fabulous.
Hey! Do you know if they make any plugins to help with SEO?
I’m trying to get my blog to rank for some targeted keywords but I’m not seeing
very good results. If you know of any please share.
Thank you!
Hi! I could have sworn I’ve been to this website before but
after browsing through some of the post I realized it’s new
to me. Anyways, I’m definitely delighted I found it and I’ll be book-marking
and checking back often!
I love reading an article that can make people think. Also,
many thanks for permitting me to comment!
It’s a shame you don’t have a donate button! I’d without a doubt donate to this superb blog! I guess for now i’ll settle for bookmarking and adding your RSS feed to my Google account. I look forward to brand new updates and will talk about this blog with my Facebook group. Talk soon!
I’m truly enjoying the design and layout of your website.
It’s a very easy on the eyes which makes it much more pleasant for me to
come here and visit more often. Did you hire out a designer to create your theme?
Superb work!
Thank you for sharing your thoughts. I truly appreciate your efforts and I will be waiting for your further write ups thank you once again.
Hi, I do believe this is an excellent web site.
I stumbledupon it 😉 I am going to come back yet again since I bookmarked it.
Money and freedom is the best way to change, may you be rich and continue to help others.
Thanks , I have recently been looking for information approximately this subject for ages
and yours is the greatest I have came upon till now.
But, what about the conclusion? Are you positive concerning
the supply?
Excellent post. Keep writing such kind of information on your blog.
Im really impressed by it.
Hey there, You’ve performed an excellent job.
I’ll definitely digg it and for my part recommend to my friends.
I’m sure they will be benefited from this web site.
Howdy would you mind letting me know which hosting
company you’re utilizing? I’ve loaded your blog in 3 completely
different browsers and I must say this blog
loads a lot quicker then most. Can you suggest a good hosting provider at a fair price?
Kudos, I appreciate it!
Heya i am for the first time here. I found this board and
I find It truly useful & it helped me out much. I hope to give something back
and aid others like you helped me.
Very energetic post, I enjoyed that a lot. Will there be a part 2?
This paragraph is actually a pleasant one it assists new internet people, who are wishing
for blogging.
I really like your blog.. very nice colors & theme.
Did you design this website yourself or did you hire someone to do it for
you? Plz answer back as I’m looking to design my own blog and would like to
find out where u got this from. thanks
Thanks for all your efforts that you have put in this. very interesting information.