B. Alyona and a tree
题意:给定一棵树,树上的边有权值为val[i],点有权值为a[i],定义dist(a,b)为a到b的路径上的边权的和
定义v控制u,当且仅当v是u的祖先且dist(u,v)<=a[u];
第一反应树形dp嘛,可行,不过感觉略麻烦。。。而且二分的还要判断一些奇怪的东西(好吧懒得打
因为u是v的后代嘛。所以dist(u,v)=dist(1,u)-dist(1,v)
所以我们先处理出dist[i]=表示dist(1,i)
然后题目的要求可以转化为:v是u的祖先且dist(1,u)-dist(1,v)<=a[u] ==》 dist(1,u)-a[u]<=dist(1,v)
这个东西貌似可以树状数组维护前缀和??
第一反应:按时间戳插入dist[i]-a[i],每次得到dist[i]作为i的答案
然而。。。。1e9
gg
换一种思路
我们按照dist[i]-a[i]插入。对于询问dist[i]
获得此时 时间戳之间的所有已经被插入的点
完全可行
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <queue> #include <string> #include <map> #include <cstring> #include <ctime> #include <vector> #define maxn 500001 #define inf 1e9 #define ll long long #define For(i,j,k) for(ll i=j;i<=k;i++) #define Dow(i,j,k) for(iny i=k;i>=j;i--) using namespace std; inline void read(ll &tx){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} tx=x*f; } inline void write(ll x){ if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x%10+'0'); } inline void writeln(ll x){write(x);puts("");} using namespace std; struct point{ll num,ki,V;} p[maxn]; bool vis[maxn]; ll f[maxn],poi[maxn],nxt[maxn],F[maxn],a[maxn],ans[maxn],n,tim,in[maxn],out[maxn],dist[maxn],v[maxn],cnt,x,y,tot; inline bool cmp(point x,point y){return x.V!=y.V?x.V<y.V:x.ki<y.ki;} inline void dfs(ll x,ll dis) { dist[x]=dis;in[x]=++tim; vis[x]=1; for(ll i=f[x];i;i=nxt[i]) if(!vis[poi[i]]) dfs(poi[i],dis+v[i]); out[x]=++tim; } inline ll lowbit(ll x){return x&-x;} inline ll get(ll x){ll sum=0;for(ll i=x;i;i-=lowbit(i)) sum+=F[i];return sum;} inline void add(ll x,ll v){for(ll i=x;i<=tim;i+=lowbit(i)) F[i]+=v;} inline void add_edge(ll x,ll y,ll z){poi[++cnt]=y;nxt[cnt]=f[x];f[x]=cnt;v[cnt]=z;} int main() { read(n); For(i,1,n) read(a[i]); For(i,1,n-1) read(x),read(y),add_edge(x,i+1,y); dfs(1,0); For(i,1,n) { point tmp; tmp.V=dist[i];tmp.ki=2;tmp.num=i; p[++tot]=tmp; tmp.V=dist[i]-a[i];tmp.ki=1; p[++tot]=tmp; } sort(p+1,p+tot+1,cmp); For(i,1,tot) { if(p[i].ki==2) ans[p[i].num]=get(out[p[i].num])-get(in[p[i].num]-1); else add(in[p[i].num],1); } For(i,1,n) write(ans[i]-1),putchar(' '); }
最后
以上就是傲娇小霸王最近收集整理的关于Codeforces Round #381 (Div. 1) B Alyona and a tree 树状数组的全部内容,更多相关Codeforces内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复