题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1023
数据生成器：http://paste.ubuntu.com/23106255/
测试数据：http://pan.baidu.com/s/1pLxVyQ3
仙人掌DP，调了好久QAQ
题解的话，让我们召唤CA爷：http://blog.csdn.net/creationaugust/article/details/48028117
值得一提的是，之前我尝试将其缩成一棵树之后，BFS两遍找直径
但wa了很久，很久。后来发现，因为走到环那里时，路径的长度是变化的，且入口不同->长度不同
所以两次BFS是错的，且无法通过多次BFS来保证正确性
换句话说，仙人掌的直径貌似只能这么DP？
另外值得一提的是，仙人掌的预处理的时候，确实只能存边，存点能找到反例（之前拍到过一组，但忘了记录下来）
换一句话来说，popoqqq的仙人掌是可以被卡掉的（好像是几个环连在一个点上）
另外的话，我仙人掌的板之前一直是错的，因为出题人数据太弱+自己数据太弱没有发现，这一份才是对的（能过neerc的数据我还是很自信的）
最后的话，仙人掌的题目，不套模板会快很多，套模板虽然代码风格统一，但写起来确实麻烦一些
#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;
}
I am really enjoying the theme/design of your web site.
Do you ever run into any browser compatibility problems?
A small number of my blog readers have complained about my site not working correctly in Explorer
but looks great in Firefox. Do you have any recommendations to help
fix this issue?
It’s very straightforward to find out any matter on web as compared to textbooks, as I found
this paragraph at this website.
I absolutely love your site.. Pleasant colors & theme. Did you develop this amazing site yourself?
Please reply back as I’m wanting to create my own blog and
would like to know where you got this from or exactly what
the theme is named. Thank you!
Hmm it seems like your blog ate my first comment
(it was extremely long) so I guess I’ll just sum it up what I wrote and
say, I’m thoroughly enjoying your blog. I too am an aspiring blog writer but I’m still new
to the whole thing. Do you have any points for beginner blog writers?
I’d definitely appreciate it.
Hello There. I found your blog using msn. This is a
very well written article. I will be sure to bookmark it
and return to read more of your useful information. Thanks for the post.
I will definitely comeback.
I’ve been browsing online greater than three hours today, but
I by no means discovered any fascinating article like yours.
It is beautiful price enough for me. Personally, if all site owners and bloggers made good
content material as you probably did, the web shall be much more helpful than ever before.
Asking questions are truly good thing if you are not understanding anything fully, except this piece of writing
presents good understanding yet.
Heya! I realize this is sort of off-topic but I needed to ask.
Does running a well-established blog such as yours take a
lot of work? I’m brand new to operating a blog but I do write in my
journal every day. I’d like to start a blog so I can easily share my personal experience and feelings online.
Please let me know if you have any suggestions or tips for
new aspiring bloggers. Thankyou!
Hi would you mind stating which blog platform you’re using?
I’m planning to start my own blog soon but I’m having a
difficult time deciding between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your layout seems different then most blogs and I’m looking
for something completely unique.
P.S Sorry for being off-topic but I had to ask!
Howdy! I know this is kind of off topic but I was
wondering which blog platform are you using for this website?
I’m getting sick and tired of WordPress because I’ve had issues
with hackers and I’m looking at alternatives for another platform.
I would be great if you could point me in the direction of a good platform.
Someone essentially help to make significantly posts I would state.
That is the first time I frequented your web page and so far?
I surprised with the analysis you made to create this particular
submit amazing. Wonderful process!
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? Outstanding work!
Hello mates, its impressive article concerning cultureand completely explained, keep it up all the time.
great post, very informative. I wonder why the other specialists of this sector don’t notice this. You must continue your writing. I’m sure, you have a huge readers’ base already!
Terrific work! That is the kind of info that should be shared across the web.
Shame on Google for now not positioning this post upper!
Come on over and visit my site . Thank you =)
I am regular reader, how are you everybody? This paragraph posted at this web page is in fact nice.
Since the admin of this website is working, no hesitation very shortly it will be well-known, due to its quality
contents.
This is really fascinating, You are an excessively skilled blogger.
I have joined your rss feed and sit up for looking for extra of your excellent post.
Additionally, I have shared your site in my social networks
The other day, while I was at work, my cousin stole my iPad and tested to see if it can survive a twenty five foot drop, just so
she can be a youtube sensation. My iPad is now destroyed and she has 83 views.
I know this is completely off topic but I had to share it with someone!
Hello to every body, it’s my first go to see of this webpage;
this website includes remarkable and truly good stuff in support of
visitors.
Amazing blog! Is your theme custom made or did you download it from somewhere?
A theme like yours with a few simple tweeks would really make my blog stand out.
Please let me know where you got your design. With thanks
I am in fact pleased to read this blog posts
which carries tons of useful information, thanks for providing such data.
Post writing is also a fun, if you be acquainted with afterward you
can write otherwise it is difficult to write.
Excellent beat ! I wish to apprentice whilst you amend your site, how could i subscribe for a
blog site? The account helped me a acceptable deal. I have been a little bit familiar of this your broadcast
provided bright transparent idea
Nice post. I was checking continuously this blog and I’m impressed!
Extremely helpful information particularly the last part 🙂 I care for such info much.
I was looking for this certain information for a long time.
Thank you and best of luck.
Touche. Sound arguments. Keep up the amazing effort.
Very interesting info !Perfect just what I was looking for! “Time is money.” by Benjamin Franklin.
I really enjoy the article.Really looking forward to read more. Really Cool.