关键词：
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3307
【题解】
这什么垃圾题啊卡空间卡时间卡栈
然后我会了一种新姿势：人工栈（好像也不难啊喂）
我们发现对于每种物品，只需要在u这地方的权值线段树上+1，v的权值线段树上+1，LCA的权值线段树上-1，LCA的父亲权值线段树上-1.
算一算就会发现符合条件了。
现在需要的就是合并线段树
线段树合并是log的，然后就是O(nlogn)了
bzoj上恰好10s。。
还有一个是，本地实测，极限数据要开到1000w才能过，bzoj卡了空间我只能开600w，居然过了。。
放两个代码吧（虽然bzoj都能过？）
直接dfs，开栈命令（？）
# pragma comment(linker, /STACK:102400000,102400000) # include <queue> # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 2e5 + 10, N = 6e6 + 10; const int mod = 1e9+7; # define RG register # define ST static namespace SMT { int p[N], w[N], ch[N][2], siz; inline void up(int x) { if(w[ch[x][0]] >= w[ch[x][1]]) { w[x] = w[ch[x][0]]; p[x] = p[ch[x][0]]; } else { w[x] = w[ch[x][1]]; p[x] = p[ch[x][1]]; } } inline void edt(int &x, int l, int r, int pos, int d) { if(!x) x = ++siz; if(l == r) { p[x] = l; w[x] += d; return ; } int mid = l+r>>1; if(pos <= mid) edt(ch[x][0], l, mid, pos, d); else edt(ch[x][1], mid+1, r, pos, d); up(x); } inline int merge(int x, int y, int l, int r) { if(!x || !y) return x+y; if(l == r) { w[x] = w[x] + w[y]; return x; } int mid = l+r>>1; ch[x][0] = merge(ch[x][0], ch[y][0], l, mid); ch[x][1] = merge(ch[x][1], ch[y][1], mid+1, r); up(x); return x; } } int head[M], nxt[M], to[M], tot=0; inline void add(int u, int v) { ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v; } inline void adde(int u, int v) { add(u, v), add(v, u); } int n, m, rt[M]; int fa[M][17], dep[M]; inline void dfs(int x, int father) { dep[x] = dep[father] + 1; fa[x][0] = father; for (int i=1; i<=16; ++i) fa[x][i] = fa[fa[x][i-1]][i-1]; for (int i=head[x]; i; i=nxt[i]) { if(to[i] == father) continue; dfs(to[i], x); } } inline int lca(int u, int v) { if(dep[u] < dep[v]) swap(u, v); for (int i=16; ~i; --i) if((dep[u]-dep[v]) & (1<<i)) u = fa[u][i]; if(u == v) return u; for (int i=16; ~i; --i) if(fa[u][i] != fa[v][i]) { u = fa[u][i]; v = fa[v][i]; } return fa[u][0]; } int ans[M]; inline void gans(int x) { for (int i=head[x]; i; i=nxt[i]) { if(to[i] == fa[x][0]) continue; gans(to[i]); rt[x] = SMT::merge(rt[x], rt[to[i]], 1, 1e9); } ans[x] = SMT::p[rt[x]]; } int main() { // freopen("3307.in", "r", stdin); // freopen("3307.out", "w", stdout); cin >> n >> m; for (int i=1, u, v; i<n; ++i) { scanf("%d%d", &u, &v); adde(u, v); } dfs(1, 0); for (int i=1, u, v, z; i<=m; ++i) { scanf("%d%d%d", &u, &v, &z); int LCA = lca(u, v); SMT::edt(rt[u], 1, 1e9, z, 1); SMT::edt(rt[v], 1, 1e9, z, 1); SMT::edt(rt[LCA], 1, 1e9, z, -1); if(LCA != 1) SMT::edt(rt[fa[LCA][0]], 1, 1e9, z, -1); } gans(1); for (int i=1; i<=n; ++i) printf("%d ", ans[i]); return 0; }
人工栈
# include <queue> # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 2e5 + 10, N = 6e6 + 10; const int mod = 1e9+7; # define RG register # define ST static namespace SMT { int p[N], w[N], ch[N][2], siz; inline void up(int x) { if(w[ch[x][0]] >= w[ch[x][1]]) { w[x] = w[ch[x][0]]; p[x] = p[ch[x][0]]; } else { w[x] = w[ch[x][1]]; p[x] = p[ch[x][1]]; } } inline void edt(int &x, int l, int r, int pos, int d) { if(!x) x = ++siz; if(l == r) { w[x] += d; if(w[x] <= 0) p[x] = 0; else p[x] = l; return ; } int mid = l+r>>1; if(pos <= mid) edt(ch[x][0], l, mid, pos, d); else edt(ch[x][1], mid+1, r, pos, d); up(x); } inline int merge(int x, int y, int l, int r) { if(!x || !y) return x+y; if(l == r) { w[x] = w[x] + w[y]; if(w[x] <= 0) p[x] = 0; else p[x] = l; return x; } int mid = l+r>>1; ch[x][0] = merge(ch[x][0], ch[y][0], l, mid); ch[x][1] = merge(ch[x][1], ch[y][1], mid+1, r); up(x); return x; } inline void prt(int x, int l, int r) { if(!x) return ; printf("%d %d %d %d %d ", x, l, r, p[x], w[x]); if(l == r) return; int mid = l+r>>1; prt(ch[x][0], l, mid); prt(ch[x][1], mid+1, r); } } int head[M], nxt[M], to[M], tot=0; inline void add(int u, int v) { ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v; } inline void adde(int u, int v) { add(u, v), add(v, u); } int n, m, rt[M]; int fa[M][17], dep[M]; bool vis[M]; queue<int> q; inline void bfs(int x) { q.push(x); dep[x] = 1; while(!q.empty()) { int top = q.front(); q.pop(); vis[top] = 1; for (int i=1; i<=16; ++i) fa[top][i] = fa[fa[top][i-1]][i-1]; for (int i=head[top]; i; i=nxt[i]) { if(!vis[to[i]]) { fa[to[i]][0] = top; dep[to[i]] = dep[top] + 1; q.push(to[i]); } } } } inline int lca(int u, int v) { if(dep[u] < dep[v]) swap(u, v); for (int i=16; ~i; --i) if((dep[u]-dep[v]) & (1<<i)) u = fa[u][i]; if(u == v) return u; for (int i=16; ~i; --i) if(fa[u][i] != fa[v][i]) { u = fa[u][i]; v = fa[v][i]; } return fa[u][0]; } int ans[M]; int st[M], cur[M], stn=0; inline void gans(int start) { int x, t; st[++stn] = start; while(stn) { x = st[stn]; if(to[cur[x]] == fa[x][0]) cur[x] = nxt[cur[x]]; if(!cur[x]) { --stn; ans[x] = SMT::p[rt[x]]; // printf("==================%d================= ", x); // SMT::prt(rt[x], 1, 1e9); t = fa[x][0]; if(t) rt[t] = SMT::merge(rt[t], rt[x], 1, 1e9); } else { t = to[cur[x]]; st[++stn] = t; cur[x] = nxt[cur[x]]; } } } int main() { // freopen("3307.in", "r", stdin); // freopen("3307.out", "w", stdout); cin >> n >> m; for (int i=1, u, v; i<n; ++i) { scanf("%d%d", &u, &v); adde(u, v); } bfs(1); for (int i=1, u, v, z; i<=m; ++i) { scanf("%d%d%d", &u, &v, &z); int LCA = lca(u, v); SMT::edt(rt[u], 1, 1e9, z, 1); SMT::edt(rt[v], 1, 1e9, z, 1); SMT::edt(rt[LCA], 1, 1e9, z, -1); if(LCA != 1) SMT::edt(rt[fa[LCA][0]], 1, 1e9, z, -1); } for (int i=1; i<=n; ++i) cur[i] = head[i]; gans(1); for (int i=1; i<=n; ++i) printf("%d ", ans[i]); return 0; } /* 5 5 1 2 2 3 3 4 4 5 1 2 1 2 3 1 1 3 1 1 4 2 3 4 2 */
bzoj3307雨天的尾巴
3307:雨天的尾巴TimeLimit: 10Sec MemoryLimit: 128MBDescriptionN个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成所有发放后，每个点存放最多的是哪种物品。... 查看详情
bzoj3307:雨天的尾巴(代码片段)
传送门树上差分+线段树合并+离散化对于修改的路径，树上差分就好了代码：#include<cstdio>#include<iostream>#include<cstring>#include<tr1/unordered_map>#include<algorithm>usingnamespacestd;voidread(int&x) 查看详情
bzoj3307雨天的尾巴
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3307【题解】这什么垃圾题啊卡空间卡时间卡栈然后我会了一种新姿势：人工栈（好像也不难啊喂）我们发现对于每种物品，只需要在u这地方的权值线段树上+1，v的权值线段树上+1，LC... 查看详情
bzoj-3307:雨天的尾巴
咱可以差分一下，把$u-v$这条路径上的$z$都加$1$变成$u$和$v$的$z$加$1$，$lca$和$fa_{lca}$的$z$减$1$。用线段树实现最大值的查询，最后$dfs$自底向上一路合并并查询即可。先开始线段树数组开小了，$RE$了一次。1#include<cassert>2#inclu... 查看详情
bzoj3307雨天的尾巴
题目链接：传送门题目大意：中文题，略题目思路：网上有题解说是合并线段树的，但是太难蒟蒻不会，只能用树剖求解 如果不是树而是一维数组我们会怎么解？ 当然是利用前缀和思想标记（... 查看详情
bzoj3307雨天的尾巴线段树合并
http://www.elijahqi.win/archives/3463DescriptionN个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成所有发放后，每个点存放最多的是哪种物品。Input第一行数字N，... 查看详情
bzoj3307雨天的尾巴（可持久化线段树合并）(代码片段)
题目大意：一颗树，想要在树链上添加同一物品，问最后每个点上哪个物品最多。解题思路：假如说物品数量少到可以暴力添加，且树点极少，我们怎么做。首先在一个树节点上标记出哪些物品有多少，寻找道路上的节点暴力添... 查看详情
[bzoj3307]雨天的尾巴(代码片段)
DescriptionN个点，形成一个树状结构。有M次发放，每次选择两个点x,y对于x到y的路径上（含x,y)每个点发一袋Z类型的物品。完成所有发放后，每个点存放最多的是哪种物品。Input第一行数字N，M接下来N-1行，每行两个数字a,b,表示a与b... 查看详情
考后反思（bzoj3940bzoj4899bzoj3307）(代码片段)
...来想用哈希只可以得20左右没想到由于数据过于水A了然后雨天的尾巴骗了5分，总分105我太菜了首先时间分配的不合理：第一题大水题ac自动机打完了都不会，第二题略微想了想打了个高斯消元，然后样例没过......，最后输出了一... 查看详情
[luogu4556]雨天的尾巴(代码片段)
[luogu4556]雨天的尾巴luogu发现是一顿子修改然后再询问,那么把修改树上差分一下再线段树合并但是...如果你只有35分...https://www.luogu.org/discuss/show/88259#include<bits/stdc++.h>usingnamespacestd;constint_=1e5+5;intre()intx=0,w=1;charch=get 查看详情
gdoi模拟雨天的尾巴树套树
雨天的尾巴深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的... 查看详情
gdoi模拟雨天的尾巴树套树
雨天的尾巴深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的... 查看详情
雨天的尾巴(代码片段)
考试的时候直接扎第一题上了这到题连暴力都没打出来T_T;心路历程：当时想到了离散化（很慌没打出来。。。），树上差分，lca倍增，当时觉滴倍增很难打，一看n<100000,于是选择用向上标记法，然而少了一行代码，，，，爆... 查看详情
gdoi2014模拟雨天的尾巴(代码片段)
题目深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被... 查看详情
[vani有约会]雨天的尾巴(代码片段)
我之前考试是遇到过这题，但是数据范围k<=20，状压就能过。结果原题范围k<=100000……果断线段树合并。普及线段树合并：比如两个相同大小的线段树,将b树各个区间上的值合并到a树上，从树根开始合并，然后递归合并左右... 查看详情
luogu4556雨天的尾巴(线段树合并+差分)(代码片段)
题目背景深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮... 查看详情
luogu4556雨天的尾巴树上差分线段树合并(代码片段)
传送门 一个套路题……树上差分+线段树合并即可注意一个细节：$pushup$的时候如果最大值为$0$一定要把最大值对应的答案也设为$0$，否则会$WA$第二个点另外如果这道题空限变小了请不要交这份代码，因为这份代码没有卡空... 查看详情
p4556[vani有约会]雨天的尾巴（线段树合并）(代码片段)
传送门一道线段树合并首先不难看出树上差分我们把每一次修改拆成四个，在(u,v)分别放上一个，在(lca)和(fa[lca])各减去一个，那么只要统计一下子树里的总数即可然而问题就在于怎么统计。直接暴力肯定是要咕咕的，那么线段... 查看详情