18年9月24日至18年9月30日
题目1：天天爱跑步
题目简述
见题面
做法简述
树上差分 + lct 乱搞
过关状态 TLE
代码
// luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 6e5 + 7; int fst[N], nxt[N], D[N << 1], w[N], deep[N], fa[N]; int son[N], top[N], size[N], csum[N], Mark[N]; int siz[N], cnt[N]; struct hh {
int from, to; }ma[N]; struct sh {
int from, to, len, lca; }mp[N]; vector<int>G[N], V[N]; int n, tot, m; inline int read() {
char c = getchar(); int f = 0; while (c < '0' || c > '9') c = getchar(); while (c >= '0' && c <= '9') f = f * 10 + c - '0', c = getchar(); return f; } void build(int f, int t) {
ma[++tot] = (hh){
f, t}; nxt[tot] = fst[f], fst[f] = tot; return; } void dfs1(int x, int f) {
deep[x] = deep[f] + 1, fa[x] = f, siz[x] = 1; for (int i = fst[x]; i; i = nxt[i]) {
int v = ma[i].to; if (v == f) continue; csum[v] = csum[x] + 1, dfs1(v, x), siz[x] += siz[v]; if (!son[x] || siz[son[x]] < siz[v]) son[x] = v; } return; } void dfs2(int x, int st) {
top[x] = st; if (!son[x]) return; dfs2(son[x], st); for (int i = fst[x]; i; i = nxt[i]) {
int v = ma[i].to; if (v == son[x] || v == fa[x]) continue; dfs2(v, v); } return; } int get_lca(int x, int y) {
int fx = top[x], fy = top[y]; while (fx != fy) {
if (deep[fx] < deep[fy]) swap(x, y), swap(fx, fy); x = fa[x], fx = top[x]; } return deep[x] > deep[y] ? y : x; } void Dfs(int x) {
int cc = D[deep[x] + w[x]], co = D[w[x] - deep[x] + N]; for (int i = fst[x]; i; i = nxt[i]) {
int v = ma[i].to; if (v == fa[x]) continue; Dfs(v); } D[deep[x]] += Mark[x]; for (int i = 0; i < V[x].size(); ++ i) {
int v = V[x][i]; D[mp[v].len - deep[mp[v].to] + N]++; } cnt[x] += D[deep[x] + w[x]] - cc + D[w[x] - deep[x] + N] - co; for (int i = 0; i < G[x].size(); ++ i) {
int v = G[x][i]; D[deep[mp[v].from]]--, D[mp[v].len - deep[mp[v].to] + N]--; } return; } void solve() {
int x, y; n = read(), m = read(); for (int i = 1; i < n; ++ i) {
x = read(), y = read(), build(x, y), build(y, x); } for (int i = 1; i <= n; ++ i) w[i] = read(); dfs1(1, 0), dfs2(1, 1); for (int i = 1; i <= m; ++ i) {
mp[i].from = read(), mp[i].to = read(); mp[i].lca = get_lca(mp[i].from, mp[i].to); mp[i].len = csum[mp[i].from] + csum[mp[i].to] - 2 * csum[mp[i].lca]; G[mp[i].lca].push_back(i), V[mp[i].to].push_back(i), Mark[mp[i].from]++; if (deep[mp[i].from] == deep[mp[i].lca] + w[mp[i].lca]) cnt[mp[i].lca]--; } Dfs(1); for (int i = 1; i <= n; ++ i) {
printf("%d ", cnt[i]); } return; } int main() {
solve(); return 0; } 讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/54691.html