网站维护的内容有哪些,重庆建站网络公司,中铁建设集团有限公司是国企吗,网站开发 加二维扫码嘟嘟嘟 这还是一道树链剖分板子题呀#xff01; 从1到n - 1枚举a[i]#xff0c;每一次使节点a[i]到a[i 1]的路径加1#xff0c;但这样的话除a[1]#xff0c;每一个点都多加了一个1#xff0c;所以输出答案的时候减1即可。 1 #includecstdio2 #includeiostrea… 嘟嘟嘟 这还是一道树链剖分板子题呀 从1到n - 1枚举a[i]每一次使节点a[i]到a[i 1]的路径加1但这样的话除a[1]每一个点都多加了一个1所以输出答案的时候减1即可。 1 #includecstdio2 #includeiostream3 #includealgorithm4 #includecmath5 #includecstring6 #includecstdlib7 #includecctype8 #includestack9 #includequeue10 #includevector11 using namespace std;12 #define enter puts()13 #define space putchar( )14 #define Mem(a) memset(a, 0, sizeof(a))15 typedef long long ll;16 typedef double db;17 const int INF 0x3f3f3f3f;18 const db eps 1e-8;19 const int maxn 3e5 5;20 inline ll read()21 {22 ll ans 0;23 char ch getchar(), last ;24 while(!isdigit(ch)) {last ch; ch getchar();}25 while(isdigit(ch)) {ans ans * 10 ch - 0; ch getchar();}26 if(last -) ans -ans;27 return ans;28 }29 inline void write(ll x)30 {31 if(x 0) putchar(-), x -x;32 if(x 10) write(x / 10);33 putchar(x % 10 0);34 }35 36 int n, a[maxn];37 vectorint v[maxn];38 39 bool vis[maxn];40 int fa[maxn], dep[maxn], size[maxn], son[maxn];41 void dfs1(int now)42 {43 vis[now] 1; size[now] 1;44 for(int i 0; i (int)v[now].size(); i)45 {46 if(!vis[v[now][i]])47 {48 fa[v[now][i]] now;49 dep[v[now][i]] dep[now] 1;50 dfs1(v[now][i]);51 size[now] size[v[now][i]];52 if(!son[now] || size[v[now][i]] size[son[now]]) son[now] v[now][i];53 }54 }55 }56 int top[maxn], dfsx[maxn], pos[maxn], cnt 0;57 void dfs2(int now)58 {59 vis[now] 1;60 dfsx[now] cnt; pos[cnt] now;61 if(son[now])62 {63 top[son[now]] top[now];64 dfs2(son[now]);65 }66 for(int i 0; i (int)v[now].size(); i)67 {68 if(!vis[v[now][i]] v[now][i] ! son[now])69 {70 top[v[now][i]] v[now][i];71 dfs2(v[now][i]);72 }73 }74 }75 76 int l[maxn 2], r[maxn 2];77 ll sum[maxn 2], lazy[maxn 2];78 void build(int L, int R, int now)79 {80 l[now] L; r[now] R;81 if(L R) return;82 int mid (L R) 1;83 build(L, mid, now 1);84 build(mid 1, R, now 1 | 1);85 }86 void pushdown(int now)87 {88 if(lazy[now])89 {90 sum[now 1] (r[now 1] - l[now 1] 1) * lazy[now];91 sum[now 1 | 1] (r[now 1 | 1] - l[now 1 | 1] 1) * lazy[now];92 lazy[now 1] lazy[now];93 lazy[now 1 | 1] lazy[now];94 lazy[now] 0;95 }96 }97 void update(int L, int R, int now)98 {99 if(l[now] L r[now] R)
100 {
101 sum[now] r[now] - l[now] 1;
102 lazy[now]; return;
103 }
104 pushdown(now);
105 int mid (l[now] r[now]) 1;
106 if(R mid) update(L, R, now 1);
107 else if(L mid) update(L ,R, now 1 | 1);
108 else {update(L, mid, now 1); update(mid 1, R, now 1 | 1);}
109 sum[now] sum[now 1] sum[now 1 | 1];
110 }
111 ll query(int id, int now)
112 {
113 if(l[now] r[now]) return sum[now];
114 pushdown(now);
115 int mid (l[now] r[now]) 1;
116 if(id mid) return query(id, now 1);
117 else return query(id, now 1 | 1);
118 }
119
120 void update2(int x, int y)
121 {
122
123 while(top[x] ! top[y])
124 {
125 if(dep[top[x]] dep[top[y]]) swap(x, y);
126 update(dfsx[top[x]], dfsx[x], 1);
127 x fa[top[x]];
128 }
129 if(dfsx[x] dfsx[y]) swap(x, y);
130 update(dfsx[x], dfsx[y], 1);
131 }
132
133 ll ans[maxn];
134
135 int main()
136 {
137 n read();
138 for(int i 1; i n; i) a[i] read();
139 for(int i 1; i n; i)
140 {
141 int x read(), y read();
142 v[x].push_back(y); v[y].push_back(x);
143 }
144 dfs1(1); Mem(vis); dfs2(1);
145 build(1, cnt, 1);
146 for(int i 1; i n; i) update2(a[i], a[i 1]);
147 for(int i 1; i n; i) {write(query(dfsx[i], 1) - (a[1] i ? 0 : 1)); enter;}
148 return 0;
149 } View Code 转载于:https://www.cnblogs.com/mrclr/p/9493498.html
