https://www.luogu.org/problemnew/show/P1600

nlogn竟然T了

#include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <map> #include <vector>using namespace std; const int N = 600001; const int oo = 99999999;#define lson jd << 1 #define rson jd << 1 | 1 #define yxy getchar() #define one_ n <= 993 #define two_ n == 99994 #define three_ n == 99995int head[N], pre[N], dis[N], tim[N], Answer[N], Askl[N], Askr[N]; bool vis[N]; int n, m, now = 1; struct Node {int u, v, w, nxt;}G[N]; queue <int> Q; vector <int> Vt[N]; int bef[N], top[N], deep[N], size[N], fa[N], son[N], tree[N], spjs; int L[N << 2], R[N << 2], W[N << 2], F[N << 2]; int ans;inline int read() {int x = 0; char c = yxy;while(c < '0' || c > '9') c = yxy;while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = yxy;return x; }inline void add(int u, int v) {G[now].v = v;G[now].nxt = head[u]; head[u] = now ++;}inline void spfa(int start,int endd) {for(int i = 1; i <= n; i ++) dis[i] = oo, vis[i] = 0;dis[start] = 0;Q.push(start);while(!Q.empty()) {int topp = Q.front(); Q.pop();vis[topp] = 0;for(int i = head[topp]; ~ i; i = G[i].nxt) {if(dis[G[i].v] > dis[topp] + 1) {dis[G[i].v] = dis[topp] + 1;pre[G[i].v] = topp;if(!vis[G[i].v]) {vis[G[i].v] = 1; Q.push(G[i].v);}}}} }void calc(int start, int endd, int diss) {int js = -1; pre[start] = 0;while(endd) {js ++;if(tim[endd] == diss - js) Answer[endd] ++;endd = pre[endd];} }void work_1() {for(int i = 1; i <= m; i ++) {spfa(Askl[i], Askr[i]);calc(Askl[i], Askr[i], dis[Askr[i]]);} }void work_2() {for(int i = 1; i <= m; i ++) Vt[Askl[i]].push_back(Askr[i]);for(int i = 1; i <= n; i ++) {int L_ = i - tim[i], R_ = i + tim[i];int siz_ = Vt[L_].size();if(L_ > 0)for(int j = 0; j < siz_; j ++) if(Vt[L_][j] >= i) Answer[i] ++;siz_ = Vt[R_].size();if(R_ <= n)for(int j = 0; j < siz_; j ++)if(Vt[R_][j] <= i) Answer[i] ++;} }void Dfs_son(int u, int f_, int dep) {printf("%d %d\n", u, f_);fa[u] = f_;deep[u] = dep;size[u] = 1;for(int i = head[u]; ~ i; i = G[i].nxt) {int v = G[i].v;if(v != f_) {Dfs_son(v, u, dep + 1);if(size[v] > size[son[u]]) son[u] = v;}} }void Dfs_un(int u, int tp){top[u] = tp;tree[u] = ++ spjs;bef[spjs] = u;if(!son[u]) return ;Dfs_un(son[u], tp);for(int i = head[u]; ~ i; i = G[i].nxt) {int v = G[i].v;if(v != fa[u] && v != son[u]) Dfs_un(v, v);} }void Sec_G(int l, int r, int jd, int x, int y) {if(x <= l && r <= y) {F[jd] ++; W[jd] += (r - l + 1); return ;}int mid = (l + r) >> 1;if(x <= mid) Sec_G(l, mid, lson, x, y);if(y > mid) Sec_G(mid + 1, r, rson, x, y);W[jd] = W[lson] + W[rson]; }void down(int jd) {F[lson] += F[jd]; F[rson] += F[jd];W[lson] += (R[lson] - L[lson] + 1) * F[jd];W[rson] += (R[rson] - L[rson] + 1) * F[jd];F[jd] = 0; }inline void Sec_G_imp(int x, int y) {int tp1 = deep[x], tp2 = deep[y];while(tp1 != tp2) {if(deep[tp1] < deep[tp2]) swap(x, y), swap(tp1, tp2);Sec_G(1, n, 1, tree[tp1], tree[x]);x = fa[tp1];tp1 = top[x];}if(deep[x] < deep[y]) swap(x, y);Sec_G(1, n, 1, tree[y], tree[x]);return ; }void Dfs_calc(int l, int r, int jd) {if(l == r) {if(deep[bef[l]] == tim[bef[l]]) Answer[bef[l]] = W[jd];return ;}if(F[jd]) down(jd);int mid = (l + r) >> 1;Dfs_calc(l, mid, lson);Dfs_calc(mid + 1, r, rson); }void work_3(){Dfs_son(1, 0, 0);Dfs_un(1, 1);for(int i = 1; i <= m; i ++) Sec_G_imp(Askl[i], Askr[i]);Dfs_calc(1, n, 1); }int main() {n = read(); m = read();for(int i = 1; i <= n; i ++) head[i] = -1;for(int i = 1; i <= n - 1; i ++) {int u = read(); int v = read(); add(u, v); add(v, u);}for(int i = 1; i <= n; i ++) tim[i] = read();for(int i = 1; i <= m; i ++) Askl[i] = read(), Askr[i] = read();if(one_) work_1();else if(two_) work_2();else if(three_) work_3();for(int i = 1; i <= n; i ++) printf("%d ", Answer[i]);return 0; }

?

轉載于:https://www.cnblogs.com/shandongs1/p/8424149.html

總結

以上是生活随笔為你收集整理的[Luogu] 1600的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。