相关链接
题目传送门:http://uoj.ac/problem/284
数据生成器:http://paste.ubuntu.com/23987506/
官方题解:http://vfleaking.blog.uoj.ac/blog/2292
解题报告
这题有一点不想写题解 _(:з」∠)_
UOJ的官方题解还是很清楚的吧?
那就偷懒不写辣!
值得一提的是,这题也是用链剖来强行优化复杂度
这个优化技巧已经多次在各种比赛中出现了
很多复杂度跟深度有关的题目都可以拿这货优化
另外,scPointer好劲啊!
都给UOJ出题了!
scPointer是我榜样!
Code
这份代码多了一个$log$
问题不是在链剖那里,而是线段树那里偷懒,多了一个二分
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 300000+9; const int M = 19; int n,m,tot,head[N],to[N],nxt[N],sz[N],pos[N]; int fa[N][M],val[N][M],hvy[N],dep[N],Val[N]; vector<pair<int,int> > q[N]; LL vout[N],sum[N]; class Segment_Tree{ int tag[N<<2],cnt; LL sum[N<<2],ans_tmp; public: inline void modify(int l, int r, int v) { modify(1, 1, n, l, r, v); } inline int query(int p) { query(1, 1, n, p); return ans_tmp; } inline LL GetSum(int l, int r) { ans_tmp = 0; GetSum(1, 1, n, l, r); return ans_tmp; } private: void push_down(int w, int l, int r) { tag[w<<1] = tag[(w<<1)+1] = tag[w]; int mid = l + r + 1 >> 1; sum[w<<1] = (LL)(mid - l) * tag[w]; sum[(w<<1)+1] = (LL)(r -mid + 1) * tag[w]; tag[w] = 0; } void modify(int w, int l, int r, int L, int R, int v) { if (L <= l && r <= R) { tag[w] = v; sum[w] = (LL)(r - l + 1) * v; } else { if (tag[w]) push_down(w, l, r); int mid = l + r + 1 >> 1; if (L < mid) modify(w<<1, l, mid-1, L, R, v); if (mid <= R) modify((w<<1)+1, mid, r, L, R, v); sum[w] = sum[w<<1] + sum[(w<<1)+1]; } } void query(int w, int l, int r, int p) { if (tag[w] || l == r) { ans_tmp = tag[w]; return; } else { int mid = l + r + 1 >> 1; if (p < mid) query(w<<1, l, mid - 1, p); else query((w<<1)+1, mid, r, p); } } void GetSum(int w, int l, int r, int L, int R) { if (L <= l && r <= R) { ans_tmp += sum[w]; } else { if (tag[w]) push_down(w, l, r); int mid = l + r + 1 >> 1; if (L < mid) GetSum(w<<1, l, mid-1, L, R); if (mid <= R) GetSum((w<<1)+1, mid, r, L, R); } } }SEG; 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 E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; } void DFS1(int w, int f) { sz[w] = 1; fa[w][0] = f; dep[w] = dep[f] + 1; val[w][0] = Val[f]; for (int i=head[w];i;i=nxt[i]) { DFS1(to[i], w); sz[w] = max(sz[w], sz[to[i]] + 1); if (sz[hvy[w]] < sz[to[i]]) hvy[w] = to[i]; } } inline int query(int x, int y) { int ret = 0; x = dep[x]; for (int j=M-1;~j;j--) { if (dep[fa[y][j]] > x) { ret = max(ret, val[y][j]); y = fa[y][j]; } } return ret; } inline int find(int l, int r, int v) { int ret = l, mid; while (l <= r) { mid = l + r >> 1; if (SEG.query(mid) < v) ret = mid, l = mid + 1; else r = mid - 1; } return ret + 1; } void DFS2(int w) { pos[w] = ++tot; if (hvy[w]) DFS2(hvy[w]); for (int i=head[w];i;i=nxt[i]) { if (to[i] != hvy[w]) { DFS2(to[i]); } } for (int i=head[w];i;i=nxt[i]) { if (to[i] != hvy[w]) { for (int j=0,p,v;j<sz[to[i]];j++) { v = SEG.query(pos[to[i]]+j); if (SEG.query(pos[w]+j+1) >= v) continue; p = find(pos[w]+j-1, pos[w]+sz[w]-1, v); SEG.modify(pos[w]+j+1, p-1, v); } } } for (int i=0,lim=q[w].size(),t,id,mx,p;i<lim;i++) { t = q[w][i].first; id = q[w][i].second; mx = query(w, t); p = find(pos[w], pos[w]+sz[w]-1, mx) - pos[w]; vout[id] = (LL)p * mx - (p?SEG.GetSum(pos[w], pos[w]+p-1):0LL) + dep[t] - dep[w]; } int p = find(pos[w], pos[w]+sz[w]-1, Val[w]); SEG.modify(pos[w], p-1, Val[w]); } int main() { n = read(); for (int i=1;i<=n;i++) Val[i] = read(); for (int i=2;i<=n;i++) Add_Edge(read(), i); m = read(); for (int i=1,s,t;i<=m;i++) { s = read(); t = read(); q[s].push_back(make_pair(t, i)); } DFS1(1, 1); for (int j=1;j<M;j++) { for (int i=1;i<=n;i++) { fa[i][j] = fa[fa[i][j-1]][j-1]; val[i][j] = max(val[i][j-1],val[fa[i][j-1]][j-1]); } } DFS2(1); for (int i=1;i<=m;i++) printf("%lld\n",vout[i]); return 0; }
Really informative article.Thanks Again. Really Cool.
Fine way of explaining, and pleasant piece of writing to obtain data regarding my presentation subject matter, which i
am going to deliver in academy.
Fastidious response in return of this query with firm arguments and describing the whole thing on the topic
of that.
Nice post. I learn something totally new and
challenging on websites I stumbleupon everyday. It’s always useful to read through content from other writers
and practice something from other web sites.
Hello! This is my first comment here so I just wanted to give a quick shout out and tell you I
genuinely enjoy reading your blog posts. Can you suggest any other blogs/websites/forums
that cover the same topics? Thanks a lot!
Thanks for sharing your thoughts on quest bars cheap.
Regards
Wow that was unusual. I just wrote an very long comment but after I clicked submit my
comment didn’t appear. Grrrr… well I’m not writing all that over again. Anyway, just wanted to say fantastic blog!
What a data of un-ambiguity and preserveness of precious familiarity
concerning unexpected emotions.
Way cool! Some very valid points! I appreciate you penning this article and the rest of the site is also really good.
Link exchange is nothing else except it is simply placing the other person’s weblog link on your page at
suitable place and other person will also do similar in support of you.
I love it when folks come together and share opinions. Great blog, stick with
it!
It’s going to be ending of mine day, but before end I am
reading this wonderful paragraph to increase my know-how.
985295 641690I like this website very a lot so considerably superb information . 679924
635035 407329Oh my goodness! a wonderful post dude. A lot of thanks Nevertheless We are experiencing difficulty with ur rss . Dont know why Can not sign up to it. Could there be anybody finding identical rss difficulty? Anyone who knows kindly respond. Thnkx 563326
Piece of writing writing is also a excitement, if you be acquainted with after that you can write or
else it is complex to write.
I think this is among the most significant info for me.
And i’m glad reading your article. But should remark on few general things, The site style is wonderful, the articles
is really nice : D. Good job, cheers
Hello to every one, the contents present at this web site are truly awesome for
people knowledge, well, keep up the nice work fellows.
I really like your writing style, superb info , thanks for posting : D.
Thanks in favor of sharing such a nice idea, post is good, thats why i have read it
fully
I love your blog.. very nice colors & theme.
Did you make this website yourself or did you hire someone to
do it for you? Plz answer back as I’m looking to construct my own blog and
would like to know where u got this from.
many thanks
Incredible! This blog looks exactly like my old
one! It’s on a completely different subject but it has pretty much the same page layout
and design. Superb choice of colors!
Thank you for the good writeup. It in fact was a amusement account it.
Look advanced to more added agreeable from you! By the way, how could we communicate?
Very nice post. I certainly love this site. Keep it
up!
I’m really loving the theme/design of your weblog. Do you
ever run into any internet browser compatibility problems?
A small number of my blog readers have complained about my website
not operating correctly in Explorer but looks great in Firefox.
Do you have any tips to help fix this issue?
I am sure this article has touched all the internet
viewers, its really really pleasant piece of writing on building up
new web site.
I got this website from my pal who shared with me on the topic of
this web page and at the moment this time I am visiting this web site and
reading very informative content here.
I consider something really interesting about your website so I saved to my bookmarks.
Im thankful for the blog.Thanks Again. Great.