【BZOJ 3672】[NOI2014] 购票

解题报告

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3672
神犇题解:http://blog.csdn.net/lych_cys/article/details/51317809

解题报告

一句话题解:树上CDQ分治

先推一推式子,发现可以斜率优化
于是我们可以用树链剖分做到$O(n \log^3 n)$
或者也可以用KD-Tree配合DFS序做到$O(n^{1.5} \log n)$

我们进一步观察,使单纯的DFS序不能做的地方在于凸包是动态的,查询也是动态的且限制了横坐标的最小值
考虑分治的话,我们按横坐标的限制排序,然后边查询边更新凸包就可以了
总的时间复杂度:$O(n \log^2 n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200009;
const int M = N << 1;
const LL INF = 6e18;

int n, head[N], nxt[M], to[M], fa[N];
LL q[N], p[N], len[N], dep[N], f[N];

struct Point{
	LL x, y, id, range;
	inline Point() {
	}
	inline Point(LL a, LL b, LL c, LL d):x(a), y(b), id(c), range(d) {
	}
	inline bool operator < (const Point &P) const {
		return x > P.x || (x == P.x && y > P.y);
	}
	inline Point operator - (const Point &P) {
		return Point(x - P.x, y - P.y, 0, 0);
	}
	inline double operator * (const Point &P) {
		return (double)x * P.y - (double)y * P.x;
	}
	inline double slope(const Point &P) {
		return (double)(y - P.y) / (x - P.x);
	}
	static bool update(const Point &P1, const Point &P2) {
		return P1.range > P2.range;
	}
};

inline LL read() {
	char c = getchar(); LL ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E; 
	to[++E] = u; nxt[E] = head[v]; head[v] = E; 
}

class DivideAndConquer{
int sz[N], vis[N];
public:	
	inline void solve(int w, int universe) {
		int top = w;
		vis[w = FindRoot(w, universe)] = 1;
		if (fa[w] && !vis[fa[w]]) {
			solve(top, universe - sz[w]);
		}
		vector<Point> cvx;
		for (int nw = fa[w]; dep[nw] >= dep[top]; nw = fa[nw]) {
			cvx.push_back(Point(dep[nw], f[nw], nw, dep[nw] - len[nw]));
		}
		vector<Point> que;
		que.push_back(Point(dep[w], 0, w, dep[w] - len[w]));
		for (int i = head[w]; i; i = nxt[i]) {
			if (dep[to[i]] > dep[w] && !vis[to[i]]) {
				DFS(to[i], w, que);
			}	
		}	
		
		sort(que.begin(), que.end(), Point::update);
		sort(cvx.begin(), cvx.end());
		for (int i = 0, j = 0, tot = 0; i < (int)que.size(); i++) {
			for (; j < (int)cvx.size() && cvx[j].x >= que[i].range; j++) {
				for (; tot > 1 && (cvx[tot - 1] - cvx[tot - 2]) * (cvx[j] - cvx[tot - 2]) >= 0; --tot);
				cvx[tot++] = cvx[j];
			}
			int ret = tot - 1, l = 0, r = tot - 2, mid, k = que[i].id;
			while (l <= r) {
				mid = l + r >> 1;
				if (cvx[mid].slope(cvx[mid + 1]) <= p[k]) {
					ret = mid;
					r = mid - 1;
				} else {
					l = mid + 1;
				}
			}
			if (ret >= 0) {
				f[k] = min(f[k], cvx[ret].y + (dep[k] - cvx[ret].x) * p[k] + q[k]);
			}
		}
		for (int i = 0, j; i < (int)que.size(); i++) {
			if (j = que[i].id, que[i].range <= dep[w]) {
				f[j] = min(f[j], f[w] + (dep[j] - dep[w]) * p[j] + q[j]);
			}
		}
		que.clear();
		cvx.clear();
	
		for (int i = head[w]; i; i = nxt[i]) {
			if (dep[to[i]] > dep[w] && !vis[to[i]]) {
				solve(to[i], sz[to[i]]);
			}
		}	
	}	
private:
	inline int FindRoot(int w, int universe) {
		int ret = 0, ans;
		FindRoot(w, w, universe, ret, ans);
		return ret;
	}	
	inline void FindRoot(int w, int f, int universe, int &ret, int &ans) {
		int mx = 1; sz[w] = 1;
		for (int i = head[w]; i; i = nxt[i]) {
			if (!vis[to[i]] && to[i] != f) {
				FindRoot(to[i], w, universe, ret, ans);
				sz[w] += sz[to[i]];
				mx = max(mx, sz[to[i]]);
			}
		}
		mx = max(mx, universe - sz[w]);
		if (!ret || mx < ans) {
			ans = mx;
			ret = w;
		}
	}
	inline void DFS(int w, int f, vector<Point> &ret) {
		ret.push_back(Point(dep[w], 0, w, dep[w] - len[w]));
		for (int i = head[w]; i; i = nxt[i]) {
			if (!vis[to[i]] && to[i] != f) {
				DFS(to[i], w, ret);
			}
		}
	}
}DAC;

int main() {
	n = read(); read();
	for (int i = 2; i <= n; i++) {
		fa[i] = read();
		LL c = read(); AddEdge(fa[i], i);
		p[i] = read(); q[i] = read();
		len[i] = read();
		dep[i] = dep[fa[i]] + c;
	}
	fill(f, f + N, INF);
	f[1] = 0; dep[0] = -1;
	DAC.solve(1, n);
	for (int i = 2; i <= n; i++) {
		printf("%lld\n", f[i]);
	}
	return 0;
}

48 thoughts to “【BZOJ 3672】[NOI2014] 购票”

  1. Today, I went to the beach with my children. I found a sea shell and gave
    it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell to her ear and screamed.
    There was a hermit crab inside and it pinched her ear.
    She never wants to go back! LoL I know this
    is completely off topic but I had to tell someone!

  2. Hello, of course this paragraph is genuinely good and I have learned lot of
    things from it on the topic of blogging. thanks.

  3. I am really enjoying the theme/design of your blog.
    Do you ever run into any web browser compatibility
    problems? A number of my blog audience have complained about my site not working correctly in Explorer but looks great in Safari.
    Do you have any solutions to help fix this issue?

  4. Wonderful goods from you, man. I have remember your stuff previous to and you’re simply too
    fantastic. I actually like what you’ve bought here, certainly like what you’re
    stating and the way in which wherein you say it. You make it entertaining and you continue to care for
    to stay it smart. I cant wait to learn far more from you.
    That is really a tremendous web site.

  5. I’m really enjoying the design and layout of your blog.
    It’s a very easy on the eyes which makes it much more enjoyable for me to come here and visit more
    often. Did you hire out a developer to create your theme?
    Exceptional work!

  6. Hey there would you mind letting me know which hosting company you’re using?
    I’ve loaded your blog in 3 completely different web browsers and I must say this blog loads a lot faster then most.
    Can you suggest a good internet hosting provider at a honest price?
    Many thanks, I appreciate it!

  7. 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 respond as I’m looking to construct my own blog and would like to find out where u got this from.

    appreciate it

  8. Hey there I am so excited I found your webpage, I really found you by mistake, while I was browsing on Askjeeve for something else, Anyways
    I am here now and would just like to say thanks for
    a remarkable post and a all round interesting blog (I also love
    the theme/design), I don’t have time to read it all at the moment but I have book-marked it and also added in your
    RSS feeds, so when I have time I will be back to read a great deal more, Please do keep up the excellent job.

  9. I’ve been browsing online more than 3 hours today, yet I
    never found any interesting article like yours.

    It is pretty worth enough for me. Personally, if all webmasters and bloggers made good content as you
    did, the net will be much more useful than ever before.

  10. I am really enjoying the theme/design of your website.
    Do you ever run into any internet browser compatibility problems?
    A couple of my blog visitors have complained about my blog not operating correctly in Explorer but looks
    great in Opera. Do you have any suggestions to help fix this issue?

  11. I absolutely love your blog and find almost all of your post’s
    to be exactly I’m looking for. Does one offer guest writers to write content for you personally?

    I wouldn’t mind writing a post or elaborating on most of the subjects you write
    regarding here. Again, awesome web site!

  12. Greetings I am so happy I found your blog, I really found you by error,
    while I was researching on Yahoo for something else, Anyways I am here now and would just like to say thanks for a incredible
    post and a all round thrilling blog (I also love the theme/design), I don’t have
    time to read through it all at the moment but I have book-marked it and also added in your RSS feeds, so when I have time I will
    be back to read a lot more, Please do keep up the superb job.

  13. 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 waste your intelligence on just posting videos
    to your blog when you could be giving us something enlightening to read?

  14. Thanks for your personal marvelous posting! I definitely enjoyed reading it, you could be a great author. I will make sure to bookmark your blog and definitely will come back someday. I want to encourage you to ultimately continue your great posts, have a nice morning!

  15. If some one wishes expert view on the topic of blogging and site-building after that i advise him/her to pay a quick visit this web site, Keep up the nice job.

  16. It’s a shame you don’t have a donate button! I’d most certainly donate to this brilliant blog! I suppose for now i’ll settle for book-marking and adding your RSS feed to my Google account. I look forward to fresh updates and will talk about this site with my Facebook group. Talk soon!

  17. I seriously love your website.. Very nice colors & theme.
    Did you create this site yourself? Please
    reply back as I’m hoping to create my own site and would love to learn where you got this from or
    exactly what the theme is named. Cheers!

  18. Hey There. I found your blog the usage of msn.
    This is a really smartly written article. I will be sure to bookmark it and come
    back to learn more of your useful information. Thank you for the post.

    I’ll certainly comeback.

  19. Awesome blog! Is your theme custom made or did you download it from somewhere?
    A design like yours with a few simple tweeks would really make my blog stand out.
    Please let me know where you got your design. Many thanks

  20. Good day! This is my first visit to your blog! We are a team
    of volunteers and starting a new project in a community in the same niche.
    Your blog provided us beneficial information to work on.
    You have done a outstanding job!

  21. I was suggested this website by my cousin. I am not sure
    whether this post is written by him as no one else know such detailed about my trouble.
    You are incredible! Thanks!

  22. Interesting blog! Is your theme custom made or did
    you download it from somewhere? A theme like yours with a
    few simple adjustements would really make my blog jump
    out. Please let me know where you got your design. Thanks

  23. Admiring the hard work you put into your website and detailed information you present.
    It’s good to come across a blog every once in a while that
    isn’t the same out of date rehashed material. Excellent read!
    I’ve bookmarked your site and I’m adding your RSS feeds to my Google account.

发表评论

电子邮件地址不会被公开。 必填项已用*标注