Codeforces Round #381 (Div. 2) D. Alyona and a tree 树上二分+前缀和思想

题目链接:

http://codeforces.com/contest/740/problem/D

D. Alyona and a tree

time limit per test2 secondsmemory limit per test256 megabytes
#### 问题描述
> Alyona has a tree with n vertices. The root of the tree is the vertex 1. In each vertex Alyona wrote an positive integer, in the vertex i she wrote ai. Moreover, the girl wrote a positive integer to every edge of the tree (possibly, different integers on different edges).
>
> Let's define dist(v, u) as the sum of the integers written on the edges of the simple path from v to u.
>
> The vertex v controls the vertex u (v ≠ u) if and only if u is in the subtree of v and dist(v, u) ≤ au.
>
> Alyona wants to settle in some vertex. In order to do this, she wants to know for each vertex v what is the number of vertices u such that v controls u.
#### 输入
> The first line contains single integer n (1 ≤ n ≤ 2·105).
>
> The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the integers written in the vertices.
>
> The next (n - 1) lines contain two integers each. The i-th of these lines contains integers pi and wi (1 ≤ pi ≤ n, 1 ≤ wi ≤ 109) — the parent of the (i + 1)-th vertex in the tree and the number written on the edge between pi and (i + 1).
>
> It is guaranteed that the given graph is a tree.
#### 输出
> Print n integers — the i-th of these numbers should be equal to the number of vertices that the i-th vertex controls
####样例输入
> 5
> 2 5 1 4 6
> 1 7
> 1 1
> 3 5
> 3 6
####样例输出
> 1 0 1 0 0

题意

给你一颗点权为a[i],的带边权的有根树(树根为1),对于节点v和它的子节点u之间,我们称v控制了u当且仅当dis(v,u)<=a[u]的时候,现在让你求每个结点能控制的子节点的个数。

题解

二分+前缀和。

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define scf scanf
#define prf printf typedef __int64 LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII; const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;
const double PI = acos(-1.0); //start---------------------------------------------------------------------- const int maxn=2e5+10;
int n;
int arr[maxn]; VPII G[maxn];
LL dep[maxn];
///ans维护的是前缀和,这里的前缀指的是从叶子到根的方向
int ans[maxn]; ///path维护当前的一条路径
vector<pair<LL,int> > path;
void dfs(int u){
///自己肯定能够的到自己
ans[u]++;
///二分找第一个dis(ancestor,u)>arr[u]既dep[u]-dep[ancestor]>arr[u]既dep[u]-arr[u]>dep[ancesotor];
int p=lower_bound(all(path),mkp(dep[u]-arr[u],-1))-path.begin()-1;
if(p>=0) ans[path[p].Y]--; path.pb(mkp(dep[u],u));
for(int i=0;i<G[u].sz();i++){
int v=G[u][i].X;
dep[v]=dep[u]+G[u][i].Y;
dfs(v);
ans[u]+=ans[v];
}
path.pop_back();
} int main(){
clr(ans,0);
scf("%d",&n);
for(int i=1;i<=n;i++) scf("%d",&arr[i]);
for(int v=2;v<=n;v++){
int u,w;
scf("%d%d",&u,&w);
G[u].pb(mkp(v,w));
} dep[1]=0;
dfs(1); for(int i=1;i<=n;i++){
prf("%d",ans[i]-1);
if(i==n) prf("\n");
else prf(" ");
} return 0;
} //end----------------------------------------------------------------------

树上倍增+前缀和

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define scf scanf
#define prf printf typedef __int64 LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII; const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;
const double PI = acos(-1.0); //start---------------------------------------------------------------------- const int maxn=2e5+10;
const int maxm=22;
int n;
int arr[maxn];
VPII G[maxn]; ///anc[i][j]表示i节点的2^j的祖先
int anc[maxn][maxm];
int ans[maxn];
LL dep[maxn];
void dfs(int u,int f){
ans[u]++;
anc[u][0]=f;
for(int i=1;i<maxm;i++){
anc[u][i]=anc[anc[u][i-1]][i-1];
} ///树上倍增
int pos=u;
for(int i=maxm-1;i>=0;i--){
int tmp=anc[pos][i];
if(dep[u]-dep[tmp]<=arr[u]){
pos=tmp;
}
} pos=anc[pos][0];
ans[pos]--; for(int i=0;i<G[u].sz();i++){
int v=G[u][i].X;
dep[v]=dep[u]+G[u][i].Y;
dfs(v,u);
ans[u]+=ans[v];
}
} int main(){
clr(ans,0);
scf("%d",&n);
for(int i=1;i<=n;i++) scf("%d",&arr[i]);
for(int v=2;v<=n;v++){
int u,w;
scf("%d%d",&u,&w);
G[u].pb(mkp(v,w));
} dep[1]=0;
dfs(1,0); for(int i=1;i<=n;i++){
prf("%d",ans[i]-1);
if(i==n) prf("\n");
else prf(" ");
} return 0;
} //end-----------------------------------------------------------------------
上一篇:Linux:自动删除n天前日志


下一篇:mysql的UseAffectedRows问题 以及其他常见配置说明