CF739B Alyona and a tree 题解报告（第一篇题解）
俗话说解每道题都是从暴力开始的嘛
刚拿到这道题时，我的第一个想法是枚举每个起点，然后向上爬，爬到多高是多高，接着我过了样例，我本来以为只是TLE，结果直接WA掉。
然而这道题的正解是：前缀和+倍增+dfs+差分
拿着每个点，先dfs跑一下深度，顺便把TA的倍增数组预处理好，然后再倍增跑一下每一个点能被控制的最远祖先，并用差分数组处理一下，最后再用dfs跑一遍把下边的值收一下（其实就相当于前缀和），就bingo了！
#include<iostream>
using namespace std;
void read(int & x)
{
x=0;int f=1;char c=getchar();
while(c>'9'||c<'0') {if(c=='-') f=-1; c=getchar();}
while(c<='9'&&c>='0')
{x=(x<<1)+(x<<3)+(c^48);c=getchar();}
x*=f;
}
void print(int x)
{
if(x<0) {putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+48);
}
int q[200005];
struct edge{
int w,to,nxt;
}e[200005];
int head[200005],cnt;
void add(int x,int y,int z)
{
cnt++;
e[cnt].w=z;
e[cnt].to=y;
e[cnt].nxt=head[x];
head[x]=cnt;
}
long long dep[200005];
int doubly[21][200005],prefix[200005];
void dfs(int s) //预处理一个倍增数组
{
for(int i=1;i<=20;i++)
doubly[i][s]=doubly[i-1][doubly[i-1][s]];
for(int i=head[s];i;i=e[i].nxt)
{
int to=e[i].to;
doubly[0][to]=s;
dep[to]=dep[s]+e[i].w;
dfs(to);
}
}
void find(int now) //找到最远的祖先
{
int x=now;
for(int i=20;i>=0;--i)
if(doubly[i][x]&&dep[now]-dep[doubly[i][x]]<=q[now])
x=doubly[i][x];
if(x!=1) prefix[doubly[0][x]]--;
if(now!=1) prefix[doubly[0][now]]++;
}
void DFS(int x)
{
for(int i=head[x];i;i=e[i].nxt)
{
int to=e[i].to;
DFS(to);
prefix[x]+=prefix[to];
}
}
int main()
{
int n;
read(n);
for(int i=1;i<=n;i++)
read(q[i]);
for(int i=2;i<=n;i++)
{
int k,g;
read(k),read(g);
add(k,i,g);
}
dfs(1);
for(int i=1;i<=n;i++) //更改差分数组
find(i);
DFS(1); //dfs一遍求前缀和
for(int i=1;i<=n;i++)
print(prefix[i]),putchar(' ');
return 0;
}