相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3924
神犇题解：http://www.cnblogs.com/clrs97/p/4779754.html
官方题解：http://wjmzbmr.com/archives/zjoi-2015-day-1题解/
解题报告
考虑从根开始向下走
如果一个儿子的子树的权值和大于总和的一半
那么所求的点一定在这个儿子的子树中
由此可见，实际上我们所求的是这样的点：
深度最大的，子树权值和大于总权值和一半的点
这样的话，暴力找复杂度不稳定
考虑树链剖分的话，可以在\({\log ^2}(n)\)的时间复杂度内找到答案
最后考虑输出解的话，似乎直接用树链剖分不行的样子
于是似乎还得用一个点分治？ (・∀・(・∀・(・∀・*)
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 100000+9;
const int M = N << 1;
const int L = 18;
const int INF = 1e9;
int n,m,head[N],nxt[M],to[M],cost[M];
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, int c) {
static int T = 0;
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = c;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = c;
}
class Heavy_Light_Decomposition{
int dep[N],dis[N],fa[N],top[N],sz[N];
int go[N],pos[N],len[N],sum,cnt;
vector<int> que[N];
class Fenwick_Tree{
#define lowbit(x) ((x)&-(x))
int arr[N];
public:
inline void modify(int l, int r, int delta) {
modify(l-1, -delta);
modify(r, delta);
}
inline int query(int p) {
LL ret = 0;
for (int i=p;i<=n;i+=lowbit(i))
ret += arr[i];
return ret;
}
private:
inline void modify(int p, int delta) {
for (int i=p;i;i-=lowbit(i))
arr[i] += delta;
}
}BIT;
public:
inline void init() {
DFS1(1, 1);
DFS2(1, 1, 1);
}
inline int DIS(int u, int v) {
int lca = LCA(u, v);
return dis[u] + dis[v] - (dis[lca] << 1);
}
inline void modify(int w, int v) {
sum += v;
for (;w;w=fa[top[w]])
BIT.modify(pos[top[w]], pos[w], v);
}
inline int query() {
int w = 1, tag = 1;
while (tag) {
int l = 1, r = len[w]-1, mid, ret = 0;
while (l <= r) {
mid = l + r >> 1;
if (BIT.query(pos[que[w][mid]])*2 <= sum) r = mid - 1;
else l = mid + 1, ret = mid;
}
w = que[w][ret]; tag = 0;
for (int i=head[w];i;i=nxt[i]) {
if (dep[to[i]] > dep[w] && BIT.query(pos[to[i]])*2 > sum) {
tag = 1; w = to[i]; break;
}
}
}
return w;
}
private:
void DFS1(int w, int f) {
sz[w] = 1; dep[w] = dep[f] + 1;
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f) {
dis[to[i]] = dis[w] + cost[i];
fa[to[i]] = w;
DFS1(to[i], w);
sz[w] += sz[to[i]];
if (sz[to[i]] > sz[go[w]])
go[w] = to[i];
}
}
}
void DFS2(int w, int f, int t) {
que[t].push_back(w);
top[w] = t; pos[w] = ++cnt;
if (go[w]) DFS2(go[w], w, t);
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f && to[i] != go[w]) {
DFS2(to[i], w, to[i]);
}
}
len[w] = que[w].size();
que[w].push_back(w);
}
inline int LCA(int u, int v) {
while (top[u] != top[v])
if (dep[top[u]] > dep[top[v]]) u = fa[top[u]];
else v = fa[top[v]];
return dep[u] > dep[v]? v: u;
}
}HLD;
class Vertex_Based_Divide_and_Conquer{
int sum[N],vis[N],len[N],fa[N][L],rod[N][L];
int root,size,cur,val_sum[N],val_sum_del[N];
LL part_ans[N],part_ans_del[N];
public:
inline void init() {
int rt = Get_Root(1, n);
len[rt] = 1;
build(rt, n);
}
inline void modify(int w, int v) {
val_sum[w] += v;
for (int i=1,p=w,d,u;i<len[w];i++) {
u = p; p = fa[w][i]; d = rod[w][i];
val_sum[p] += v;
val_sum_del[u] += v;
part_ans[p] += (LL)v * d;
part_ans_del[u] += (LL)v * d;
}
}
inline LL query(int w) {
LL ret = part_ans[w];
for (int i=1,p=w,u,d;i<len[w];i++) {
u = p; p = fa[w][i]; d = rod[w][i];
ret += part_ans[p] + (LL)val_sum[p] * d;
ret -= part_ans_del[u] + (LL)val_sum_del[u] * d;
}
return ret;
}
private:
inline int Get_Root(int w, int sz) {
size = sz; cur = INF;
Get_root(w, w);
return root;
}
void Get_root(int w, int f) {
int mx = 1; sum[w] = 1;
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, size - sum[w]);
if (mx < cur) cur = mx, root = w;
}
void build(int w, int sz) {
vis[w] = 1; fa[w][0] = w;
for (int i=1;i<len[w];i++)
rod[w][i] = HLD.DIS(w, fa[w][i]);
for (int i=head[w],tmp,rt;i;i=nxt[i]) {
if (!vis[to[i]]) {
tmp = sum[to[i]]<sum[w]? sum[to[i]]: sz-sum[w];
rt = Get_Root(to[i], tmp);
len[rt] = len[w] + 1;
memcpy(fa[rt]+1, fa[w], sizeof(int)*len[w]);
build(rt, tmp);
}
}
}
}VDC;
int main() {
n = read(); m = read();
for (int i=1,u,v;i<n;i++) {
u = read(); v = read();
Add_Edge(u, v, read());
}
HLD.init();
VDC.init();
for (int i=1,p,v;i<=m;i++) {
p = read(); v = read();
HLD.modify(p, v);
VDC.modify(p, v);
p = HLD.query();
printf("%lld\n",VDC.query(p));
}
return 0;
}
哇塞，居然是沙发？留个名
Hi there, all is going fine here and ofcourse every one is sharing facts,
that’s genuinely fine, keep up writing.
Appreciate the recommendation. Will try it out.
It is in point of fact a nice and useful piece
of information. I am happy that you just shared this useful information with us.
Please stay us up to date like this. Thank you for sharing.
Everything is very open with a very clear explanation of the issues.
It was really informative. Your website is useful.
Many thanks for sharing!
I am really pleased to glance at this blog posts which contains tons
of helpful information, thanks for providing such data.
I am not sure where you’re getting your info, but great topic.
I needs to spend some time learning more or understanding more.
Thanks for wonderful information I was looking for this info for my mission.
May I simply just say what a comfort to uncover somebody who truly understands what they’re discussing on the web.
You actually know how to bring an issue to light and make it important.
A lot more people really need to look at this and understand
this side of the story. I can’t believe you are not more popular given that you most certainly have the gift.
Hi! I realize this is somewhat off-topic however I had to
ask. Does running a well-established website like yours take a lot of work?
I am completely new to writing a blog however I do write in my journal everyday.
I’d like to start a blog so I can easily share my personal experience and thoughts online.
Please let me know if you have any kind of recommendations or tips for brand new aspiring bloggers.
Appreciate it!
Hi, I would like to subscribe for this webpage to obtain newest
updates, therefore where can i do it please help out.
Spot on with this write-up, I actually feel this site needs much more attention. I’ll probably be
returning to read through more, thanks for the info!
wonderful post, very informative. I wonder why the opposite experts of this sector do not realize this.
You must proceed your writing. I am confident, you have a huge readers’
base already!
Awesome! Its actually awesome paragraph, I have got much clear
idea concerning from this piece of writing.
Oh my goodness! Incredible article dude! Thank you, However I am experiencing difficulties with
your RSS. I don’t understand why I cannot subscribe to
it. Is there anyone else getting the same RSS issues? Anyone
that knows the solution can you kindly respond? Thanks!!
I’ve been browsing on-line more than three hours today, but I never discovered any interesting article like yours. It is lovely worth sufficient for me. In my view, if all website owners and bloggers made just right content as you did, the net can be much more useful than ever before.
This article will assist the internet visitors for building up new weblog or even a weblog from start to end.
Everything is very open with a very clear explanation of the challenges.
It was truly informative. Your website is very helpful.
Thanks for sharing!
I know this web site gives quality depending articles and additional data, is there any
other site which presents these data in quality?
Its like you read my thoughts! You seem to understand so much approximately
this, such as you wrote the ebook in it or something.
I think that you simply can do with some percent to drive the message house a little bit, however instead
of that, this is wonderful blog. An excellent read. I will certainly be back.
If you wish for to improve your familiarity only
keep visiting this web site and be updated with the most up-to-date
gossip posted here.
Thank you for sharing your info. I really appreciate your efforts and
I am waiting for your further write ups thanks
once again.
What’s up to every one, it’s actually a fastidious for me to
pay a quick visit this website, it consists of useful Information.
I believe this website has got some rattling superb info for everyone. “The penalty of success is to be bored by the attentions of people who formerly snubbed you.” by Mary Wilson Little.