题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2851
数据生成器:http://paste.ubuntu.com/23321973/
如果考虑{ai}为父亲集合的话
这货是个DAG
然后看一看{bi}中涉及到的∩操作
从顶端向下考虑的话,这™不就是支配点!
于是求一求灾难树,然后求一求路径并
话说这么巧妙的题目出题人是怎么想到的!
服! 真心服!
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 200000+9; const int M = N*200; int head[N],nxt[M],to[M],n,m,in[N],out[N]; int que[N],fa[N][18],dep[N],num_cnt; vector<int> G[N]; 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) { static int T = 0; in[v]++; to[++T] = v; nxt[T] = head[u]; head[u] = T; } inline bool cmp(const int &a, const int &b) { return in[a] < in[b]; } inline int lca(int x, int y) { if (dep[x] < dep[y]) swap(x, y); for (int i=17;~i;i--) { if (dep[fa[x][i]] >= dep[y]) { x = fa[x][i]; } } if (x == y) return y; for (int i=17;~i;i--) { if (fa[x][i] != fa[y][i]) { x = fa[x][i]; y = fa[y][i]; } } return fa[x][0]; } inline void solve(int w) { dep[w] = dep[fa[w][0]] + 1; if (w) G[fa[w][0]].push_back(w); for (int i=1;i<=17;i++) { fa[w][i] = fa[fa[w][i-1]][i-1]; } for (int i=head[w];i;i=nxt[i]) { if (!~fa[to[i]][0]) { fa[to[i]][0] = w; } else { fa[to[i]][0] = lca(fa[to[i]][0], w); } if (!--in[to[i]]) solve(to[i]); } } void DFS(int w) { in[w] = ++num_cnt; for (int i=G[w].size()-1;~i;i--) { DFS(G[w][i]); } out[w] = num_cnt; } int main(){ memset(fa,-1,sizeof(fa)); n = read(); for (int i=1;i<=n;i++) { for (int j=read();j;j--) { Add_Edge(read(),i); } if (!in[i]) { Add_Edge(0,i); } } fa[0][0] = 0; solve(0); DFS(0); m = read(); for (int k=1,len,vout=0;k<=m;k++,vout=0) { len = read(); for (int j=1;j<=len;j++) { que[j] = read(); } sort(que+1,que+1+len,cmp); for (int i=1,pre=0;i<=len;i++) { vout += dep[que[i]]; vout -= dep[lca(pre,que[i])]; pre = que[i]; } printf("%d\n",vout); } return 0; }
—– UPD 2016.10.16 —–
今天发现这题数据范围有问题
关系数应该是小于2e6
点数应该是小于2e5
Hi there! Someone in my Myspace group shared this site with us so I came to take a
look. I’m definitely loving the information. I’m
bookmarking and will be tweeting this to my followers! Great blog and brilliant design.
I got this website from my friend who told me regarding this
web page and now this time I am browsing this
site and reading very informative articles
here.
Have you ever thought about writing an e-book or guest authoring on other websites?
I have a blog based on the same ideas you discuss and would love to have you share
some stories/information. I know my visitors
would enjoy your work. If you’re even remotely interested, feel free to
shoot me an email.
I would like to thank you for the efforts you have put in writing
this site. I really hope to view the same high-grade content by
you later on as well. In fact, your creative writing abilities has inspired me to get my own, personal blog now 😉
Write more, thats all I have to say. Literally, it
seems as though you relied on the video to make your point.
You clearly know what youre talking about, why throw away your
intelligence on just posting videos to your blog when you could be
giving us something enlightening to read?
Your style is unique in comparison to other folks I’ve read
stuff from. I appreciate you for posting when you’ve got the opportunity,
Guess I’ll just bookmark this page.
At this time it sounds like Movable Type is the preferred blogging platform out there right now.
(from what I’ve read) Is that what you are using on your blog?
Definitely believe that which you stated. Your favorite reason appeared to be on the web the simplest thing to be aware of. I say to you, I certainly get irked while people consider worries that they just don’t know about. You managed to hit the nail upon the top and also defined out the whole thing without having side effect , people could take a signal. Will likely be back to get more. Thanks
Nice blog here! Also your web site loads up fast!
What web host are you using? Can I get your affiliate link to your host?
I wish my web site loaded up as fast as yours
lol
I am really impressed with your writing skills as
well as with the layout on your blog. Is this a paid theme
or did you modify it yourself? Anyway keep up the excellent
quality writing, it’s rare to see a nice blog like this
one today.
I’m not sure why but this weblog is loading very slow for
me. Is anyone else having this problem or is it
a issue on my end? I’ll check back later on and see if the
problem still exists.
After looking over a handful of the articles on your site, I truly appreciate your
technique of writing a blog. I saved it to my bookmark site list and will be checking back soon. Please
visit my website as well and tell me how you feel.
Very good blog! Do you have any tips for aspiring writers?
I’m planning to start my own site soon but I’m a little lost on everything.
Would you advise starting with a free platform like WordPress or go for a paid option? There are so many choices out there that I’m completely confused ..
Any suggestions? Thanks a lot!
I constantly spent my half an hour to read this blog’s content daily along
with a cup of coffee.
Greetings! Very helpful advice in this particular article!
It’s the little changes that will make the most important changes.
Thanks a lot for sharing!
This post presents clear idea in favor of the new users
of blogging, that truly how to do blogging.
A fascinating discussion is worth comment. I think that you should write more on this subject
matter, it may not be a taboo matter but generally people don’t
speak about these topics. To the next! Best wishes!!
It’s going to be end of mine day, but before end I am reading this great piece of writing to increase my know-how.
hello!,I love your writing so a lot! percentage we communicate more about your article on AOL?
I need a specialist in this area to unravel my problem.
Maybe that’s you! Having a look ahead to see you.
I know this web site gives quality depending content and other data,
is there any other web site which gives these kinds of information in quality?
hello!,I like your writing very much! share we communicate more about your article on AOL? I need an expert on this area to solve my problem. Maybe that’s you! Looking forward to see you.