Description
給定一棵以1為根的有根樹,初始所有節點顔色為1,每次将距離節點a不超過l的a的子節點染成c,或詢問點a的顔色
Input
第一行一個數T,表示資料組數 接下來每組資料的第一行三個數n,c,q表示結點個數,顔色數和操作數 接下來一行n-1個數描述2..n的父節點 接下來q行每行三個數a,l,c 若c為0,表示詢問a的顔色 否則将距離a不超過l的a的子節點染成c
Output
設目前是第i個操作,y_i為本次詢問的答案(若本次操作是一個修改則y_i為0),令z_i=i*y_i,請輸出z_1+z_2+...+z_q模10^9+7
Sample Input
1
4 3 7
1 2 2
3 0 0
2 1 3
3 0 0
1 0 2
2 0 0
4 1 1
4 0 0
Sample Output
32
HINT
第1,3,5,7的詢問的答案分别為1,3,3,1,是以答案為 1*1+2*0+3*3+4*0+5*3+6*0+7*1=32. 資料範圍: 對于100%的資料T<=6,n,m,c<=10^5, 1<=a<=n,0<=l<=n,0<=c<=c
Solution
将每個點看成二維點$(DFN[x],Depth[x])$，也就是$DFS$序和深度。
這樣的話這個題就變成了單點查詢和區間打标記覆寫了。
區間打标記的時候記得把路徑上經過的點顔色修改一下……因為這裡挂了調了好久（
Code
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<algorithm>
5 #define N (100009)
6 #define MOD (1000000007)
7 using namespace std;
8
9 struct Edge{int to,next;}edge[N];
10 int T,n,c,q,x,a,l,opt,ans,dfs_num,D,MaxDep;
11 int DFN[N],Depth[N],Size[N];
12 int head[N],num_edge;
13
14 struct Node
15 {
16 int Max[2],Min[2],d[2],ls,rs,col,cov;
17 bool operator < (const Node &a) const {return d[D]<a.d[D];}
18 }p[N],Q;
19
20 struct KDT
21 {
22 Node T[N];
23 void Pushup(int now)
24 {
25 int ls=T[now].ls,rs=T[now].rs;
26 for (int i=0; i<=1; ++i)
27 {
28 T[now].Max[i]=T[now].Min[i]=T[now].d[i];
29 if (ls)
30 {
31 T[now].Max[i]=max(T[now].Max[i],T[ls].Max[i]);
32 T[now].Min[i]=min(T[now].Min[i],T[ls].Min[i]);
33 }
34 if (rs)
35 {
36 T[now].Max[i]=max(T[now].Max[i],T[rs].Max[i]);
37 T[now].Min[i]=min(T[now].Min[i],T[rs].Min[i]);
38 }
39 }
40 }
41 void Pushdown(int now)
42 {
43 if (T[now].cov!=-1)
44 {
45 int ls=T[now].ls,rs=T[now].rs;
46 T[ls].cov=T[ls].col=T[now].cov;
47 T[rs].cov=T[rs].col=T[now].cov;
48 T[now].cov=-1;
49 }
50 }
51 int Build(int opt,int l,int r)
52 {
53 if (l>r) return 0;
54 int mid=(l+r)>>1;
55 D=opt; nth_element(p+l,p+mid,p+r+1);
56 T[mid]=p[mid];
57 T[mid].ls=Build(opt^1,l,mid-1);
58 T[mid].rs=Build(opt^1,mid+1,r);
59 Pushup(mid); return mid;
60 }
61 int Query(int now)
62 {
63 if (Q.d[0]<T[now].Min[0] || Q.d[0]>T[now].Max[0]) return 0;
64 if (Q.d[1]<T[now].Min[1] || Q.d[1]>T[now].Max[1]) return 0;
65 if (Q.d[0]==T[now].d[0] && Q.d[1]==T[now].d[1]) return T[now].col;
66 Pushdown(now); return Query(T[now].ls)+Query(T[now].rs);
67 }
68 void Update(int now,int k)
69 {
70 if (Q.Min[0]>T[now].Max[0] || Q.Max[0]<T[now].Min[0] || Q.Min[1]>T[now].Max[1] || Q.Max[1]<T[now].Min[1]) return;
71 if (Q.Min[0]<=T[now].Min[0] && Q.Max[0]>=T[now].Max[0] && Q.Min[1]<=T[now].Min[1] && Q.Max[1]>=T[now].Max[1])
72 {
73 T[now].col=k; T[now].cov=k;
74 return;
75 }
76 Pushdown(now);
77 if (T[now].d[0]>=Q.Min[0] && T[now].d[0]<=Q.Max[0] && T[now].d[1]>=Q.Min[1] && T[now].d[1]<=Q.Max[1])
78 T[now].col=k;
79 Update(T[now].ls,k); Update(T[now].rs,k);
80 }
81 }KDT;
82
83 inline int read()
84 {
85 int x=0; char c=getchar();
86 while (c<'0' || c>'9') c=getchar();
87 while (c>='0' && c<='9') x=x*10+c-'0', c=getchar();
88 return x;
89 }
90
91 void add(int u,int v)
92 {
93 edge[++num_edge].to=v;
94 edge[num_edge].next=head[u];
95 head[u]=num_edge;
96 }
97
98 void DFS(int x)
99 {
100 Size[x]=1; DFN[x]=++dfs_num;
101 for (int i=head[x]; i; i=edge[i].next)
102 {
103 Depth[edge[i].to]=Depth[x]+1;
104 DFS(edge[i].to);
105 Size[x]+=Size[edge[i].to];
106 }
107 MaxDep=max(MaxDep,Depth[x]);
108 }
109
110 int main()
111 {
112 T=read();
113 while (T--)
114 {
115 memset(head,0,sizeof(head));
116 memset(Depth,0,sizeof(Depth));
117 num_edge=dfs_num=MaxDep=ans=0;
118 n=read(); c=read(); q=read();
119 for (int i=1; i<=n; ++i)
120 p[i].col=1, p[i].cov=-1;
121 for (int i=2; i<=n; ++i)
122 x=read(), add(x,i);
123 DFS(1);
124 for (int i=1; i<=n; ++i)
125 p[i].d[0]=DFN[i], p[i].d[1]=Depth[i];
126 int Root=KDT.Build(0,1,n);
127 for (int i=1; i<=q; ++i)
128 {
129 a=read(); l=read(); opt=read();
130 if (opt==0)
131 {
132 Q.d[0]=DFN[a]; Q.d[1]=Depth[a];
133 (ans+=1ll*i*KDT.Query(Root)%MOD)%=MOD;
134 }
135 else
136 {
137 Q.Min[0]=DFN[a]; Q.Max[0]=DFN[a]+Size[a]-1;
138 Q.Min[1]=Depth[a]; Q.Max[1]=min(MaxDep,Depth[a]+l);
139 KDT.Update(Root,opt);
140 }
141 }
142 printf("%d\n",ans);
143 }
144 } 轉載于:https://www.cnblogs.com/refun/p/10226010.html