Task 1：关联点

【问题描述】

 ⼆叉树是⼀种常用的数据结构，⼀个⼆叉树或者为空，或者由根节点、左⼦树、右⼦树构成，其中左⼦树和右⼦树都是⼆叉树. 每个节点a 可以存储⼀个值val.

 显然，如果⼀个点a 的左⼦树或右⼦树内有⼀个点b，那么存在唯⼀的路径从a 出发，每次往左⼦树或右⼦树⾛，经过⼀系列节点访问到b. 我们把从a 到b 经过除a 以外的节点数称为节点a 到节点b 的距离.

 对于⼀个点a，定义：

 若点\(b\) 在\(a\) 的左⼦树中，且\(a\) 到\(b\) 的距离为\(v[b]\)，则称\(b\) 为\(a\) 的左关联点；

 若点\(b\) 在\(a\) 的右⼦树中，且\(a\) 到\(b\) 的距离为\(v[b]\)，则称\(b\) 为\(a\) 的右关联点.

 给定⼀个共有\(n\) 个节点的⼆叉树，所有节点编号为\(1, 2, ...,n，\)其中1 为根节点. 给出每个节点\(a\) 存储的值\(v[a]\)，请输出每个节点的左关联点个数和右关联点个数.

【输入格式】

 输⼊⽂件名为\(node.in\)

 第⼀⾏⼀个正整数\(n\)，表示⼆叉树的总节点数.

 第⼆⾏\(n\) 个由空格分隔的正整数\(v1,v2,..., vn\)第\(i\) 个数\(vi\) 表示节点\(i\) 存储的值.

 接下来\(n\) ⾏，第\(i\) ⾏为两个由空格分隔的整数，分别表示编号为\(i\) 的左⼦树的根节点（若左⼦树为空则为0）和右⼦树的根节点（若右⼦树为空则为0）.

【输出格式】

 输出⽂件名为\(node.out\)

 输出\(n\) ⾏，第\(i\) ⾏为两个整数，分别表示点\(i\) 的左关联点个数和右关联点个数.

node.in	node.out
5	2 0
2 1 3 2 1	0 1
2 3	0 0
4 5	0 0
0 0	0 0
0 0
0 0

【样例说明】

 节点1 的左关联点有2 个：2 和4，没有右关联点.

 节点2 没有左关联点，右关联点有1 个：5.

 除此之外，其它节点没有关联点.

【数据规模与约定】

• 对于30% 的数据，\(n <= 3\).
• 对于60% 的数据，\(n <= 500\).
• 对于100% 的数据，\(n <= 200000，1 <= vi <= 200000\)，根节点1 到任意节点的距离不超过100000.

 题目本身不难理解，这里给出四种写法思路：

• 暴力O（n^2）（60pts），直接模拟某个点\(u\)向上找\(val[ u ]\)的节点，记录答案
• 倍增O（nlogn），暴力基础上的优化，以更快的速度向上寻找节点记录答案
• 堆O（nlogn），在向下搜索的时候把该节点对应的父节点扔进堆里维护，按dfn排序，到达时退栈即可
• 栈O（n），由于搜索本身就是入栈退栈的过程，只需要搜索同时维护一个栈就可以O(1)找到答案。

 本蒻的代码里写的是第三种。后三种代码都是可以AC的，但栈的写法才是最优秀的。比较简单不做赘述。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define MAXN 200010using namespace std;int n,arr[MAXN],ans_1[MAXN],ans_2[MAXN],dfn[MAXN];struct Node{int ls,rs,fa;}node[MAXN];struct Rec{    int deep;    bool operator<(const Rec &rhs)const{        return deep
         
          que;void pre(int u,int deep){ dfn[u]=deep; if(node[u].ls!=0)pre(node[u].ls,deep+1); if(node[u].rs!=0)pre(node[u].rs,deep+1);}void dfs(int u){ if(node[u].ls!=0)dfs(node[u].ls); if(node[u].rs!=0)dfs(node[u].rs); //backstack; que.push((Rec){dfn[u]-arr[u]});// printf("nod=%d deep=%d dfn=%d\n",u,que.top().deep,dfn[u]); while(que.top().deep==dfn[u]-1&&!que.empty()){ if(u==node[node[u].fa].ls){// printf("l:fa=%d\n",node[u].fa); ans_1[node[u].fa]++; }else{// printf("r:fa=%d\n",node[u].fa); ans_2[node[u].fa]++; } que.pop(); }}int main(){ freopen("node.in","r",stdin); freopen("node.out","w",stdout); scanf("%d",&n); memset(node,0,sizeof(node)); for(int i=1;i<=n;++i){ scanf("%d",&arr[i]); } for(int i=1;i<=n;++i){ scanf("%d",&node[i].ls); scanf("%d",&node[i].rs); node[node[i].ls].fa=i; node[node[i].rs].fa=i;//record father } pre(1,0); dfs(1);// for(int i=1;i<=n;++i)printf("%d ",dfn[i]); for(int i=1;i<=n;++i){ printf("%d %d\n",ans_1[i],ans_2[i]); }}
         
        
       
      
     
    

---

Task 2：小奇的日程表

【问题描述】

 放暑假了，小奇准备了⼀个日程表来安排他的暑假⽣活.

 ⼀共有n 件事情，编号为\(1，2......n\)，第\(i\) 件事情的难度为\(i\). 小奇将整个暑假划分为m 个时刻，并设定了三个正整数\(a，b，c.\) 然后，小奇定义了⼀个数列\({ xi }\)，满⾜：

  $x[0] = 0 $

  \(x [i] = (a x[ i - 1 ] + b) \% 2nc (1 <= i <= m)\)

 即从x1 开始，数列的每⼀项等于上⼀项的a 倍加上b 以后除以2nc 的余数.

 在暑假刚开始时，小奇的日程表是空的. 第i 个时刻前，小奇会根据xi 的值决定日程表的变化：

 若\(xi < nc\)，则将编号为$⌊ xi / c ⌋ + 1 $的事件加⼊日程表，若日程表已有该事件则忽略；

 若\(xi >= nc\)，则将编号为$⌊ xi / c ⌋ - n + 1 $的事件从日程表删除，若日程表没有该事件则忽略；

 第i 个时刻\(（1 <= i <= m）\)，小奇所做的事情就是该时刻日程表中的所有事件.

 对于每个时刻，小奇定义该时刻的⼯作量为该时刻做了⼏件事情，该时刻的疲劳度为该时刻做的所有事情的难度之和. 整个暑假小奇的⼯作量为所有时刻的⼯作量之和，疲劳度为所有时刻的疲劳度之和.

 请根据$n，m，a，b，c $计算小奇这个暑假的⼯作量和疲劳度.

【输入格式】

 输⼊⽂件名为\(schedule.in\)

 输⼊⼀⾏，五个由空格分隔的正整数\(n，m，a，b，c\)

【输出格式】

 输出⽂件名为\(schedule.out\)

 ⼀⾏两个由空格分隔的整数，第⼀个数为小奇这个暑假的⼯作量，第⼆个数为小奇这个暑假的疲劳度.

 由于答案可能很⼤，请输出答案除以1000000007 的余数.

【样例输入1】

​ 3 6 4 1 5

【样例输出1】

​ 8 13

【样例输入2】

​ 431942 2000000 324635 9496472 24439

【样例输出2】

​ 879995658 63186390

【样例1 说明】

 由\(x0 = 0，xi = (4x[ i - 1 ] + 1) mod 30（1 <= i <= 6）\)

 可推得\(x1 = 1，x2 = 5，x3 = 21，x4 = 25，x5 = 11，x6 = 15\).

 第1 个时刻，日程表加⼊事件1，该时刻的事件有{ 1 }，⼯作量为1，疲劳度为1.

 第2 个时刻，日程表加⼊事件2，该时刻的事件有{ 1，2 }，⼯作量为2，疲劳度为1 + 2 = 3.

 第3 个时刻，日程表删除事件2，该时刻的事件有{ 1 }，⼯作量为1，疲劳度为1.

 第4 个时刻，日程表删除事件3，该时刻的事件有{ 1 }，⼯作量为1，疲劳度为1.

 第5 个时刻，日程表加⼊事件3，该时刻的事件有{ 1，3 }，⼯作量为2，疲劳度为1 + 3 = 4.

 第6 个时刻，日程表删除事件1，该时刻的事件有{ 3 }，⼯作量为1，疲劳度为3.

 因此总⼯作量为1+2+1+1+2+1 = 8，总疲劳度为1+3+1+1+4+3 = 13.

【数据规模与约定】

• \(对于40\% 的数据，n，m <= 10^3.\)
• \(对于60\% 的数据，n，m <= 10^5.\)
• \(另外有20\% 的数据，保证所有删除均可忽略.\)
• \(对于100\% 的数据，n <= 5*10^7，m <= 2*10^6，a <= 10^6，b <= 10^9，c <= 5*10^4.\)

 语文题，不用动脑子，动脑子会绕弯，题目让干啥你就干啥就可以了。

 有些人想的是用set来存储，但仔细观察会发现实际上只需要一个bool数组就可以了，还不会爆空间，多好啊。

 

#include
    
     #include
     
      #include
      
       #include
       
        #define MAXM 2000010#define MAXN 50000010#define lint long longusing namespace std;lint n,m,a,b,c,ans_1,ans_2,sum_1,sum_2,arr[MAXM],f[MAXM];bool vis[MAXN];int main(){    freopen("schedule.in","r",stdin);    freopen("schedule.out","w",stdout);    cin>>n>>m>>a>>b>>c;    const lint modd=n*c*2,cmp=n*c;    for(register int i=1;i<=m;++i){        f[i]=(a*f[i-1]+b)%modd;        if(f[i]
       
      
     
    

Task 3：送分题

【问题描述】

 给定⼀棵N 个节点的树，每个节点上有⼀个权值。

 你要从中选出⼀些点使得权值和最⼤，任意2 个选出的节点之间的距离都要⼤于K。

【输入格式】

 输⼊⽂件名为score.in

 第⼀⾏两个整数\(N，K\)。

 接下来⼀⾏\(N\) 个整数，表示第\(i\) 个节点的权值

 接下来\(N - 1\) ⾏，每⾏2 个数\(a，b\)，表示点\(a\)和点\(b\) 之间有边相连

【输出格式】

输出⽂件名为\(score.out\)

输出⼀⾏，表示最⼤的权值和。

【样例输入1】

​ 3 1

​ 1 1 1

​ 1 2

​ 1 3

【样例输出1】

​ 2

【样例输入2】

​ 3 2

​ 1 1 1

​ 1 2

​ 1 3

【样例输出2】

​ 1

【数据范围】

​ \(n∈[1,10000]，k∈[1,100]\)

 这是一道送命题。

 状态可以很容易就想到：设\(f[ u ][ j ]\)为当前位于点\(u\)，子树里最近的选中节点离自身距离大于等于\(j\)。

 但是状态的转移设计起来就相当麻烦，或者说，说起来容易写起来难。思路如下：

• 对于\(j*2>k\)的时候，我们可以随便选着转移。（直接累加求\(max\)即可）

• 对于\(j*2<=k\)的时候，我们需要这样考虑：

  • 选出一个点距离为\(j\)
  • 其它点的距离都应该大于\(k-j\)
  • 显然除了有一个点距离为j，其它点距离都是k-j
  • 考虑预先累加求一定距离时的权值和，需要开一个辅助数组tmp
  • 转移结束后需要维护一下后缀最大值，让f[ u ][ j ]是子树点离u点距离>=j的最大权值
  • 其余的就是常规的树上DP了

 不写一遍你不会知道这个看起来简单的思路写起来有多难受，至少状态转移方程的推导真的让人无从下手。思路我最开始都能想出来，但是实现不了。结果看题解的代码，完全就是有机会要上，没机会创造机会也要硬上。。我果然还是Naive啊。。

​ Code：代码里注释很清晰

#include
    
     #include
     
      #define MAXN 10010int n,dis,cnt,tmp[110],v[MAXN],g[MAXN][110],head[MAXN];struct edge{    int nxt;    int to;}e[MAXN<<1];inline void add(int from,int to){    e[++cnt].nxt=head[from];    e[cnt].to=to;    head[from]=cnt;} inline int max(int x,int y){return x>y?x:y;}inline int min(int x,int y){return x
      
       =(j<<1)){                g[u][j]=max(g[u][j],tmp[dis-j]-g[v][dis-j-1]+g[v][j-1]);            }//若j不足以直接多次选择，本次点又要考虑选距离为j的情况             //就通过这种方法选择         }        if((j<<1)>=dis){            g[u][j]=max(g[u][j],tmp[j]);        }//反之，如果可以直接处理，事情就变得相当简单。     }    for(int j=dis;j>=0;j--){        g[u][j]=max(g[u][j],g[u][j+1]);    }//维护一个后缀最大值 }int main(){    freopen("score.in","r",stdin);    freopen("score.out","w",stdout);    scanf("%d%d",&n,&dis);dis++;//输入时把dis+1便于计算     for(int i=1;i<=n;++i){        scanf("%d",&v[i]);//输入每个点的权值     }    for(int i=1;i