相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1095
数据生成器：http://paste.ubuntu.com/23659435/
神犇题解：http://blog.csdn.net/PoPoQQQ/article/details/44461423
解题报告
先建出点分树，再考虑维护三种堆
一种堆用来维护到点i的子树中所有点到点i的父亲的距离
然后第二种堆维护每一个儿子的第一种堆的最大值
第三种堆，维护所有第二种堆的最大值
酱紫话，查询之际输出第三个堆的堆顶
修改的话，就暴力在点分树上向上爬，边爬边修改
话说这题真™难写啊！
从上午11：00写到晚上12：00
真是日了哮天犬了！
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 100000+9;
const int M = N << 1;
const int INF = 1e9;
int head[N],to[M],nxt[M],n,m;
char pat[10],sta[N];
inline int read() {
char c=getchar(); int f=1,ret=0;
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) {
static int T = 0;
to[++T] = v; nxt[T] = head[u]; head[u] = T;
to[++T] = u; nxt[T] = head[v]; head[v] = T;
}
namespace Dynamic_Node_Decomposition{
#define DND Dynamic_Node_Decomposition
int cur,root,node_sz,cnt,in[N];
int fa[N][18],sum[N],dep[N],len[N],vis[N];
multiset<int> vout,s1[N],s2[N];
multiset<int>::iterator itr;
namespace Sparse_Table{
#define ST Sparse_Table
int _fa[N][18];
inline void init() {
for (int i=1;i<=17;i++) {
for (int j=1;j<=n;j++) {
_fa[j][i] = _fa[_fa[j][i-1]][i-1];
}
}
}
inline int query(int u, int v) {
int ret = dep[u] + dep[v];
if (dep[u] < dep[v]) swap(u, v);
for (int i=17;~i;i--) {
if (dep[_fa[u][i]] >= dep[v]) {
u = _fa[u][i];
}
}
if (u == v) return ret - dep[u] * 2;
for (int i=17;~i;i--) {
if (_fa[u][i] != _fa[v][i]) {
u = _fa[u][i];
v = _fa[v][i];
}
}
return ret - dep[_fa[u][0]] * 2;
}
};
void Get_root(int w, int f) {
sum[w] = 1; int mx = 0;
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f && !vis[to[i]]) {
Get_root(to[i], w);
sum[w] += sum[to[i]];
mx = max(mx, sum[to[i]]);
}
}
mx = max(mx, node_sz - sum[w]);
if (mx < cur) cur = mx, root = w;
} inline int Get_Root(int w, int SZ) {
cur = INF; node_sz = SZ;
Get_root(w,-1);
return root;
}
#define Delete(x, y) itr = x.lower_bound(y), x.erase(itr)
#define Max(x) (x.size()? itr = x.end(), *--itr : -1)
inline int Ans(multiset<int> &TMP) {
if (TMP.size() < 2) return -1;
else {
int ret = *--(itr=TMP.end());
ret += *--itr;
if (*itr <= -1) return -1;
else return ret;
}
}
inline void modify(int w, int ty) {
if (ty) cnt++; else cnt--;
for (int i=0;i<len[w];i++)
if (sta[fa[w][i]])
Delete(vout, Max(s2[fa[w][i]]));
for (int i=len[w]-2,t1,t2,dis,tmp;~i;i--) {
t1 = fa[w][i]; t2 = fa[w][i+1];
dis = ST::query(w, t2);
tmp = Max(s1[t1]);
if (tmp = (tmp <= dis)) {
Delete(vout, Ans(s2[t2]));
Delete(s2[t2], Max(s1[t1]));
}
if (!ty) Delete(s1[t1], dis);
else s1[t1].insert(dis);
if (tmp) {
s2[t2].insert(Max(s1[t1]));
vout.insert(Ans(s2[t2]));
}
}
sta[w] ^= ty >= 0;
for (int i=0;i<len[w];i++)
if (sta[fa[w][i]])
vout.insert(Max(s2[fa[w][i]]));
}
inline int query() {
if (cnt == 0) return -1;
else if (cnt == 1) return 0;
else return Max(vout);
}
void DFS(int w, int f) {
dep[w] = dep[f] + 1; ST::_fa[w][0] = f;
for (int i=head[w];i;i=nxt[i])
if (to[i] != f) DFS(to[i], w);
} void Build(int w, int sz, int sur) {
Get_Root(w,sz);
vis[w=root] = 1;
len[w] = len[sur] + 1;
fa[w][0] = root;
memcpy(fa[w]+1,fa[sur],sizeof(fa[w])-4);
for (int i=head[w];i;i=nxt[i])
if (!vis[to[i]])
Build(to[i], sum[to[i]], w);
} inline void init() {
Build(1, n, 0);
DFS(1, 1);
ST::init();
fill(sta+1, sta+1+n, 1);
for (int i=1;i<=n;i++) {
s2[fa[i][1]].insert(-1);
vout.insert(-1);
vout.insert(-1);
}
for (int i=1;i<=n;i++)
modify(i, -1);
}
};
int main() {
n = read();
for (int i=1;i<n;i++)
Add_Edge(read(), read());
DND::init();
m = read();
for (int i=1,p;i<=m;i++) {
scanf("%s",pat+1);
if (pat[1] == 'C') {
p = read();
if (sta[p]) DND::modify(p, 0);
else DND::modify(p, 1);
} else {
printf("%d\n",DND::query());
}
}
return 0;
}
原谅我为了好写而各种封装而造成的巨大常数 QwQ
Everyone loves it when individuals come together and share opinions.
Great blog, continue the good work!
Awesome post.
Hello there, You’ve done a great job. I’ll certainly digg it and personally suggest to my friends.
I’m confident they will be benefited from
this web site.
I am regular visitor, how are you everybody? This paragraph posted at this web page is genuinely nice.
It’s going to be ending of mine day, but before ending I am reading this enormous post to improve my experience.
Hi there! This article could not be written any better!
Looking at this post reminds me of my previous roommate!
He constantly kept preaching about this. I most certainly will forward this article to
him. Fairly certain he’s going to have a very good read.
Thanks for sharing!
Unquestionably believe that which you said. Your
favorite justification appeared to be on the web the simplest thing to remember of.
I say to you, I certainly get annoyed even as folks
consider concerns that they plainly do not recognise about.
You managed to hit the nail upon the highest and
also outlined out the entire thing with no need side-effects , people can take a signal.
Will likely be again to get more. Thank you
Good day! I could have sworn I’ve been to this site before
but after reading through some of the post I realized it’s
new to me. Nonetheless, I’m definitely delighted I found
it and I’ll be bookmarking and checking back often!
Wonderful goods from you, man. I’ve understand your stuff previous
to and you’re just extremely excellent. I actually like what you have acquired here, certainly like what you’re stating and the way in which you
say it. You make it entertaining and you still take care of to keep it sensible.
I cant wait to read far more from you. This is actually a wonderful web site.
Great post, I believe website owners should acquire a lot from this blog its very user friendly.
Have you ever considered writing an e-book or guest authoring on other
sites? I have a blog based upon on the same information you discuss
and would love to have you share some stories/information. I know my audience would value your work.
If you’re even remotely interested, feel free to send me an e mail.
You actually make it seem so easy with your presentation but I find this matter to be
really something that I think I would never understand.
It seems too complex and extremely broad for me. I’m looking forward for your next post,
I will try to get the hang of it!
Appreciate this post. Will try it out.
My family members always say that I am wasting my time here at net,
however I know I am getting know-how daily by
reading thes pleasant articles or reviews.
Howdy I am so happy I found your webpage, I really found you
by mistake, while I was researching on Digg for something else,
Nonetheless I am here now and would just like to say thank you for a fantastic
post and a all round entertaining blog (I also love the theme/design), I don’t have time to read it all at the minute but
I have bookmarked it and also included your RSS feeds,
so when I have time I will be back to read a lot more, Please do keep up
the excellent jo.
This paragraph will help the internet viewers for creating new web site
or even a weblog from start to end.
If some one wishes expert view on the topic of running a blog then i propose him/her to pay a quick visit this weblog, Keep up the good job.
hi!,I love your writing very much! proportion we communicate extra about your post on AOL?
I need an expert on this space to solve my problem.
Maybe that’s you! Taking a look forward to peer you.
That is very interesting, You are an excessively professional blogger.
I have joined your feed and look forward to searching for more of your excellent post.
Additionally, I have shared your website in my social networks
If some one desires expert view about blogging and site-building after that i propose him/her
to visit this website, Keep up the nice job.
Greetings! This is my 1st comment here so I just wanted to give a
quick shout out and say I really enjoy reading your blog posts.
Can you suggest any other blogs/websites/forums
that go over the same subjects? Thanks!
Hello there, I do think your website could be
having web browser compatibility issues. When I
look at your site in Safari, it looks fine however, when opening in Internet Explorer, it’s got some overlapping issues.
I just wanted to give you a quick heads up! Besides that,
excellent site!
Can you tell us more about this? I’d want to find out more details.
Hi colleagues, how is the whole thing, and what
you want to say regarding this paragraph, in my view its actually remarkable
for me.
Great ?V I should definitely pronounce, impressed with your website. I had no trouble navigating through all tabs and related information ended up being truly simple to do to access. I recently found what I hoped for before you know it at all. Quite unusual. Is likely to appreciate it for those who add forums or anything, site theme . a tones way for your client to communicate. Nice task..
Very informative blog.Really looking forward to read more. Awesome.
Thanks-a-mundo for the blog post.Thanks Again. Will read on…