青出于蓝胜于蓝(jisuanke)
武当派一共有 nn 人，门派内 nn 人按照武功高低进行排名，武功最高的人排名第 11，次高的人排名第 22，... 武功最低的人排名第 nn。现在我们用武功的排名来给每个人标号，除了祖师爷，每个人都有一个师父，每个人可能有多个徒弟。
我们知道，武当派人才辈出，连祖师爷的武功都只能排行到 pp。也就是说徒弟的武功是可能超过师父的，所谓的青出于蓝胜于蓝。
请你帮忙计算每个人的所有子弟（包括徒弟的徒弟，徒弟的徒弟的徒弟....）中，有多少人的武功超过了他自己。
输入格式
输入第一行两个整数 n, p(1 \le n \le 100000, 1 \le p \le n)n,p(1≤n≤100000,1≤p≤n)。
接下来 n-1n−1 行，每行输入两个整数 u, v(1 \le u, v \le n)u,v(1≤u,v≤n)，表示 uu 和 vv 之间存在师徒关系。
输出格式
输出一行 nn 个整数，第 ii 个整数表示武功排行为 ii 的人的子弟有多少人超过了他。
行末不要输出多余的空格。
样例输入复制
10 55 35 83 43 12 16 78 79 88 10
样例输出复制
0 0 2 0 4 0 1 2 0 0
其实就是查询区间(l,r]有几个。由于是从名次第一开始，所以往后的名次只要在dfs序中有值便是名次比自己高但是是自己的徒弟，如果不在同一子树上，会因为dfs序的r[i]所分开，到最后只是算dfs在(l,r]这个区间的值
#include#include using namespace std;const int N=1e5+5,MD=1e9+7;int L[N],R[N],c[N];int tot,n;vector G[N];void dfs(int u,int fa)//处理出dfs序{ L[u]=++tot; for(auto X:G[u])if(X!=fa)dfs(X,u); R[u]=tot;}void add(int x,int val){ for(int i=x; i<=n; i+=(i&-i)) c[i]+=val;}int Sum(int x){ int ans=0; for(int i=x; i; i-=(i&-i)) ans+=c[i]; return ans;}int main(){ int rt; scanf("%d%d",&n,&rt); for(int i=2,u,v; i<=n; i++) scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u); tot=0; dfs(rt,-1); for(int i=1;i
链接：
来源：牛客网题目描述
输入描述:
输入测试组数T，每组数据，输入n+1行整数，第一行为n和p，1<=n<=20000, 1<=p<=n, 接下来n-1行，每行两个整数u和v,表示u和v之间有一条边。第n+1行输入n个整数val1, val2,…, valn,其中1<=vali<=10000，1<=i<=n.
输出描述:
对于每组数据，输出一行，包含1个整数， 表示对1000000007取模后的结果
输入
25 45 32 54 21 310 4 3 10 53 31 32 11 10 1
输出
112
备注:
n>=10000的有20组测试数据
先预处理合数的倍数，然后就是dfs序了
#includeusing namespace std;typedef long long ll;const ll MD=1e9+7;vector v[20020],d[10005];int n,rt,vis[10005];ll val[20020],ans,f[20020];void dfs(int x,int pre){ for(auto X:d[val[x]])f[X]=(f[X]+x)%MD; ans=(ans+f[val[x]])%MD; for(auto X:v[x])if(X!=pre)dfs(X,x); for(auto X:d[val[x]])f[X]=(f[X]-x+MD)%MD;}int main(){ for(int i=2; i<=10000; i++) if(!vis[i])for(int j=i+i; j<=10000; j+=i)vis[j]=1; for(int i=4; i<=10000; i++) if(vis[i])for(int j=i; j<=10000; j+=i)d[j].push_back(i); int T; cin>>T; while(T--) { ans=0; cin>>n>>rt; memset(vis,0,sizeof vis); for(int i=1; i<=n; i++)v[i].clear(); for(int i=1,x,y; i >x>>y,v[x].push_back(y),v[y].push_back(x); for(int i=1; i<=n; i++)cin>>val[i]; dfs(rt,-1); cout< <<'\n'; }}
Change
There is a rooted tree with n nodes, number from 1-n. Root’s number is 1.Each node has a value ai.
Initially all the node’s value is 0.
We have q operations. There are two kinds of operations.
1 v x k : a[v]+=x , a[v’]+=x-k (v’ is child of v) , a[v’’]+=x-2*k (v’’ is child of v’) and so on.
2 v : Output a[v] mod 1000000007(10^9 + 7).
Input
First line contains an integer T (1 ≤ T ≤ 3), represents there are T test cases.
In each test case:
The first line contains a number n.
The second line contains n-1 number, p2,p3,…,pn . pi is the father of i.
The third line contains a number q.
Next q lines, each line contains an operation. (“1 v x k” or “2 v”)
1 ≤ n ≤ 3*10^5
1 ≤ pi < i
1 ≤ q ≤ 3*10^5
1 ≤ v ≤ n; 0 ≤ x < 10^9 + 7; 0 ≤ k < 10^9 + 7
Output
For each operation 2, outputs the answer.
Sample Input
131 131 1 2 12 12 2
Sample Output
21
这个题目的题意还是很简单的，就是一个访问x，就把它+x，他的孩子要多减去k，孙子多减2k
可以考虑用两个树状数组维护，一个维护x+deep[v]*k，一个-k
#include#include using namespace std;const int N=3e5+5,MD=1e9+7;int L[N],R[N],deep[N],n;int a[N],b[N];int tot;vector G[N];void dfs(int u)//处理出dfs序与每个点的深度{ L[u]=++tot; int l=G[u].size(); for(int i=0,v; i