[SPOJ-QTREE2]Query on a tree II 题解
题目地址:洛谷:【SP913】QTREE2 – Query on a tree …
May all the beauty be blessed.
题目地址:Codeforces:Problem – 100633D – Codeforces
The Large Wood Database is created to securely store and paint any existing tree. Update for LWDB provides new functionality, so it is time to think over the graph theory. A weighed tree is stored in the LWDB. In the query language for LWDB Management System (LWDB MS) two types of queries are available:
It is required to prototype LWDB MS and respond to all user’s queries.
给你一棵带边权的树,要求操作1.改变一个节点d距离内的所有点颜色为c;2.询问一个点颜色。
输入格式:
The first line contains an integer N (1 ≤ N ≤ 105) — the number of tree vertices. The following N-1 lines contain the description of branches, three numbers in each line ai, bi, wi (1 ≤ ai, bi ≤ N, ai ≠ bi, 1 ≤ wi ≤ 104), where i-th branch with weight wi connects vertices ai and bi. The next line contains integer Q (1 ≤ Q ≤ 105) — number of queries. In each of Q following lines there are two types of queries:
Input numbers are integers.
输出格式:
For each second type query output the color of requested vertice in a separate line.
输入样例#1:
5 1 2 30 1 3 50 3 4 70 3 5 60 8 1 3 72 6 2 5 1 4 60 5 2 3 2 2 1 2 144 7 2 4 2 5
输出样例#1:
6 6 0 5 7
对于这道题,我们在点分树上统计的信息变成了每一次染色操作。
对于一个距离为d,染色点为u的染色操作,我们在它到树根这条链上的重心打标记,直到u到某个重心的距离超出了染色距离。标记的含义是,从这个重心出发的若干距离范围内的点都被打上标记。在每个重心维护一个单调栈,使得栈内标记的作用范围d以时间顺序单调递减。
查询时,也从查询点u往根走,二分找到能影响到这个点的标记,维护当前找到的最新标记,该标记就是最终给这个点染色的标记。
可以脑补一下这个过程来意识流证明其正确性。
下面的代码参考了【Codeforces 100633D】LWDB – Qizy’s Database。Qizy同学的代码还是非常优美的。利用预处理和倍增减小常数,实现的抽象和封装也很优美。学习了。
// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
char c = fgc();
while(c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 100005, INF = 1e9;
int fa[MAXN][20], dep[MAXN], dis[MAXN];
struct Edge {
int to, w;
};
std::vector<Edge> gra[MAXN];
inline void dfs(int u, int f) {
fa[u][0] = f;
dep[u] = dep[f] + 1;
for(Edge e : gra[u]) {
int v = e.to, w = e.w;
if(v == f) continue;
dis[v] = dis[u] + w;
dfs(v, u);
}
}
inline int caldis(int u, int v) {
int res = dis[u] + dis[v];
if(dep[u] < dep[v]) std::swap(u, v);
for(int i = 19; i >= 0; i--) {
if(dep[fa[u][i]] >= dep[v]) u = fa[u][i];
}
if(u == v) return res - (dis[u] << 1);
for(int i = 19; i >= 0; i--) {
if(fa[u][i] != fa[v][i]) {
u = fa[u][i];
v = fa[v][i];
}
}
return res - (dis[fa[u][0]] << 1);
}
int sum, rt, rod[MAXN][20], siz[MAXN], msz[MAXN], anc[MAXN][20], len[MAXN];
bool vis[MAXN];
struct Data {
int dis, col, id;
inline bool operator<(const Data &rhs) const {
return dis < rhs.dis;
}
inline bool operator<=(const Data &rhs) const {
return dis <= rhs.dis;
}
};
Data tmp;
std::vector<Data> stk[MAXN];
std::vector<Data>::reverse_iterator it;
inline void getrt(int u, int fa) {
siz[u] = 1;
msz[u] = 0;
for(Edge e : gra[u]) {
int v = e.to;
if(v == fa || vis[v]) continue;
getrt(v, u);
siz[u] += siz[v];
msz[u] = std::max(msz[u], siz[v]);
}
msz[u] = std::max(msz[u], sum - siz[u]);
if(msz[u] < msz[rt]) rt = u;
}
inline void dac(int u) {
anc[u][0] = u;
vis[u] = true;
for(Edge e : gra[u]) {
int v = e.to;
if(vis[v]) continue;
sum = siz[v];
rt = 0;
getrt(v, u);
len[rt] = len[u] + 1;
memcpy(anc[rt] + 1, anc[u], sizeof(anc[u]) - 4);
dac(rt);
}
for(int i = 1; i < len[u]; i++) {
rod[u][i] = caldis(u, anc[u][i]);
}
}
inline void modify(int u, int d, int col, int id) {
tmp.col = col; tmp.id = id;
for(int i = 0; i < len[u]; i++) {
int f = anc[u][i];
tmp.dis = d - rod[u][i];
if(tmp.dis >= 0) {
while(!stk[f].empty() && stk[f].back() <= tmp) stk[f].pop_back();
stk[f].push_back(tmp);
}
}
}
inline int query(int u) {
Data res = {0, 0, 0};
for(int i = 0; i < len[u]; i++) {
int f = anc[u][i]; tmp.dis = rod[u][i];
it = std::lower_bound(stk[f].rbegin(), stk[f].rend(), tmp);
if(it != stk[f].rend() && res.id < it->id) res = *it;
}
return res.col;
}
int n, ut, vt, wt, m, op, dt, ct;
int main() {
n = readint();
for(int i = 1; i < n; i++) {
ut = readint(); vt = readint(); wt = readint();
gra[ut].push_back(Edge {vt, wt});
gra[vt].push_back(Edge {ut, wt});
}
dfs(1, 1);
for(int k = 1; k < 20; k++) {
for(int i = 1; i <= n; i++) {
fa[i][k] = fa[fa[i][k - 1]][k - 1];
}
}
msz[0] = INF;
sum = n;
rt = 0;
getrt(1, 0);
len[rt] = 1;
dac(rt);
m = readint();
for(int i = 1; i <= m; i++) {
op = readint();
if(op == 1) {
ut = readint(); dt = readint(); ct = readint();
modify(ut, dt, ct, i);
} else {
ut = readint();
printf("%d\n", query(ut));
}
}
return 0;
}
题目地址:洛谷:【P4178】Tree – 洛谷、BZOJ:Problem 1468. — Tree
给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K
输入格式:
N(n<=40000) 接下来n-1行边描述管道,按照题目中写的输入 接下来是k
输出格式:
一行,有多少对点之间的距离小于等于k
输入样例#1:
7 1 6 13 6 3 9 3 5 7 4 1 3 2 4 20 4 7 2 10
输出样例#1:
5
点分治的板子。下面只说统计答案的思路。
我们考虑每一对儿子,计算其经过根的路径。如果按照【P3806】【模板】点分治1 – 洛谷这道题O(n^2)地统计答案可能有些吃力,我们要把统计答案改为O(n)算法,即维护两个指针l和r来拼出答案。但是这样计算会有不合法的情况,即两个儿子在同一子树内。那么我们考虑递归到子树里面去把这些不合法的答案减掉。递归下去以后还要把所有儿子的距离加上子树-根这条边的边权的2倍。
// Code by KSkun, 2018/3
#include <cstdio>
#include <vector>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
char c = fgc();
while(c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 40005, INF = 1e9;
int n, m, ut, vt, wt, k, rt, res = 0;
int siz[MAXN], dep[MAXN], msz[MAXN], sum;
bool vis[MAXN];
struct Edge {
int to, w;
};
std::vector<Edge> gra[MAXN];
int ans[MAXN], atot = 0;
inline void getroot(int u, int fa) {
siz[u] = 1; msz[u] = 0;
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i].to;
if(vis[v] || v == fa) continue;
getroot(v, u);
siz[u] += siz[v];
msz[u] = std::max(msz[u], siz[v]);
}
msz[u] = std::max(msz[u], sum - siz[u]);
if(msz[u] < msz[rt]) rt = u;
}
inline void caldep(int u, int fa) {
ans[atot++] = dep[u];
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i].to, w = gra[u][i].w;
if(vis[v] || v == fa) continue;
dep[v] = dep[u] + w;
caldep(v, u);
}
}
inline int work(int u, int w) {
atot = 0;
dep[u] = w;
caldep(u, 0);
std::sort(ans, ans + atot);
int l = 0, r = atot - 1;
int resw = 0;
while(l < r) {
if(ans[l] + ans[r] <= k) {
resw += r - l;
l++;
} else {
r--;
}
}
return resw;
}
inline void dfs(int u) {
res += work(u, 0);
vis[u] = true;
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i].to, w = gra[u][i].w;
if(vis[v]) continue;
res -= work(v, w);
rt = 0;
sum = siz[v];
getroot(v, 0);
dfs(rt);
}
}
int main() {
n = readint();
for(int i = 1; i < n; i++) {
ut = readint(); vt = readint(); wt = readint();
gra[ut].push_back(Edge {vt, wt});
gra[vt].push_back(Edge {ut, wt});
}
k = readint();
rt = 0;
msz[0] = INF;
sum = n;
getroot(1, 0);
dfs(rt);
printf("%d", res);
return 0;
}
题目地址:洛谷:【P3178】[HAOI2015]树上操作 – 洛谷、BZOJ:Problem 4034. — [HAOI2015]树上操作
有一棵点数为 N 的树,以点 1 为根,且树点有边权。然后有 M 个操作,分为三种:
操作 1 :把某个节点 x 的点权增加 a 。
操作 2 :把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 :询问某个节点 x 到根的路径中所有点的点权和。
输入格式:
第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数,表示树中节点的初始权值。接下来 N-1 行每行两个正整数 from, to , 表示该树中存在一条边 (from, to) 。再接下来 M 行,每行分别表示一次操作。其中第一个数表示该操作的种类( 1-3 ) ,之后接这个操作的参数( x 或者 x a ) 。
输出格式:
对于每个询问操作,输出该询问的答案。答案之间用换行隔开。
输入样例#1:
5 5 1 2 3 4 5 1 2 1 4 2 3 2 5 3 3 1 2 1 3 5 2 1 2 3 3
输出样例#1:
6 9 13
对于 100% 的数据, N,M<=100000 ,且所有输入数据的绝对值都不会超过 10^6 。
比树剖那篇文章的例题还裸。
// Code by KSkun, 2018/3
#include <cstdio>
#include <vector>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
char c = fgc();
while(c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 100005;
int n, m, w[MAXN], ut, vt, op, xt, at;
int fa[MAXN], siz[MAXN], son[MAXN], dfn[MAXN], ptn[MAXN], top[MAXN], dep[MAXN], cnt;
std::vector<int> gra[MAXN];
inline void addedge(int u, int v) {
gra[u].push_back(v);
gra[v].push_back(u);
}
inline void dfs1(int u) {
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
if(v == fa[u]) continue;
dep[v] = dep[u] + 1;
fa[v] = u;
dfs1(v);
siz[u] += siz[v] + 1;
if(siz[v] > siz[son[u]]) son[u] = v;
}
}
inline void dfs2(int u, int tp) {
top[u] = tp;
dfn[u] = ++cnt;
ptn[dfn[u]] = u;
if(son[u]) dfs2(son[u], tp);
for(int i = 0; i < gra[u].size(); i++) {
int v = gra[u][i];
if(v == son[u] || v == fa[u]) continue;
dfs2(v, v);
}
}
struct Node {
LL val, add;
} sgt[MAXN << 2];
inline void pushdown(int o, int l, int r) {
int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
if(sgt[o].add) {
sgt[lch].add += sgt[o].add;
sgt[rch].add += sgt[o].add;
sgt[lch].val += sgt[o].add * (mid - l + 1);
sgt[rch].val += sgt[o].add * (r - mid);
sgt[o].add = 0;
}
}
inline void build(int o, int l, int r) {
if(l == r) {
sgt[o].val = w[ptn[l]];
return;
}
int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
build(lch, l, mid);
build(rch, mid + 1, r);
sgt[o].val = sgt[lch].val + sgt[rch].val;
}
inline void add(int o, int l, int r, int ll, int rr, LL v) {
if(l >= ll && r <= rr) {
sgt[o].add += v;
sgt[o].val += v * (r - l + 1);
return;
}
pushdown(o, l, r);
int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
if(ll <= mid) add(lch, l, mid, ll, rr, v);
if(rr > mid) add(rch, mid + 1, r, ll, rr, v);
sgt[o].val = sgt[lch].val + sgt[rch].val;
}
inline LL query(int o, int l, int r, int ll, int rr) {
if(l >= ll && r <= rr) {
return sgt[o].val;
}
pushdown(o, l, r);
LL res = 0;
int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
if(ll <= mid) res += query(lch, l, mid, ll, rr);
if(rr > mid) res += query(rch, mid + 1, r, ll, rr);
return res;
}
inline void addpoint(int x, LL v) {
add(1, 1, n, dfn[x], dfn[x], v);
}
inline void addsubtree(int x, LL v) {
add(1, 1, n, dfn[x], dfn[x] + siz[x], v);
}
inline LL querychain(int x) {
int tp = top[x];
LL res = 0;
while(x) {
res += query(1, 1, n, dfn[tp], dfn[x]);
x = fa[tp];
tp = top[x];
}
return res;
}
int main() {
n = readint(); m = readint();
for(int i = 1; i <= n; i++) w[i] = readint();
for(int i = 1; i < n; i++) {
ut = readint(); vt = readint();
addedge(ut, vt);
}
dfs1(1);
dfs2(1, 1);
build(1, 1, n);
while(m--) {
op = readint();
xt = readint();
if(op != 3) at = readint();
if(op == 1) {
addpoint(xt, at);
}
if(op == 2) {
addsubtree(xt, at);
}
if(op == 3) {
printf("%lld\n", querychain(xt));
}
}
return 0;
}