相关链接
题目传送门: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; }