真·NOIp day1 T2
众所周知noip按难度顺序出题
感谢洛谷题解&＃64;greenlcat 提供思路及写法
写&＃43;调&＃43;写题解 共计一整个晚上2.5个小时对我今天晚自习啥都没干
分步解决这个题
Step 1 :倍增LCA
本身这题码量就不小&＃xff0c;还写树剖LCA&＃xff0c;我这个菜鸡调不出来的
倍增求LCA好像没什么可写的&＃xff0c;基本操作
1 int n,m,cnt,deep[maxn],fa[maxn][25],w[maxn],head[maxn];
2 struct edge{
3 int nxt,to;
4 }e[maxn*2];
5 inline void add(int from,int to){
6 e[&＃43;&＃43;cnt].to&＃61;to;e[cnt].nxt&＃61;head[from];head[from]&＃61;cnt;
7 }
8 void dfs1(int x){
9 for(int i&＃61;1;(1<
10 fa[x][i]&＃61;fa[fa[x][i-1]][i-1];
11 }
12 for(int i&＃61;head[x];i;i&＃61;e[i].nxt){
13 int y&＃61;e[i].to;
14 if(y&＃61;&＃61;fa[x][0])continue;
15 fa[y][0]&＃61;x;
16 deep[y]&＃61;deep[x]&＃43;1;
17 dfs1(y);
18 }
19 }
20 int lca(int x,int y){
21 if(x&＃61;&＃61;y)return x;
22 if(deep[x]<deep[y])swap(x,y);
23 int k&＃61;log(deep[x]-deep[y])/log(2);
24 for(int i&＃61;k;i>&＃61;0;i--){
25 if(deep[fa[x][i]]>&＃61;deep[y]){
26 x&＃61;fa[x][i];
27 }
28 if(x&＃61;&＃61;y)return x;
29 }
30 k&＃61;log(deep[x])/log(2);
31 for(int i&＃61;k;i>&＃61;0;i--){
32 if(fa[x][i]!&＃61;fa[y][i]){
33 x&＃61;fa[x][i];y&＃61;fa[y][i];
34 }
35 }
36 return fa[x][0];
37 }
38 int main(){
39 n&＃61;read();m&＃61;read();
40 for(int i&＃61;1;i
41 int u,v;u&＃61;read();v&＃61;read();
42 add(u,v);add(v,u);
43 }
44 deep[1]&＃61;1;fa[1][0]&＃61;1;dfs1(1);
45 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){
46 w[i]&＃61;read();
47 }
48 return 0;
49 }
Step 2 :分析转化
发现模拟每个玩家的复杂度爆炸&＃xff0c;分着不行就考虑整体处理
改为枚举每个观察员&＃xff0c;看哪些节点对观察员有贡献&＃xff08;可被观察到&＃xff09;
而枚举观察员可以转化成dfs整棵树&＃xff0c;O(n)可以接受
考虑对于一个观察员x&＃xff0c;如果他在一条$s_i$到$t_i$的路径上
1.如果x在$s_i$到LCA上
当$s_i$满足$deep[{s_i}]&＃61;w[x]&＃43;deep[x]$时&＃xff0c;$s_i$对x有1的贡献
2.如果x在$t_i$到LCA上
当$t_i$满足$dis[{s_i},{t_i}]-deep[{t_i}]&＃61;w[x]-deep[x]$时&＃xff0c;$t_i$对x有1的贡献
所以我们发现&＃xff0c;能够对x有贡献的$s_i$或$t_i$都在以x为根的子树上
Step 3 :统计贡献
code&＃xff08;注释都在代码里了&＃xff09;
1 struct edge{
2 int nxt,to;
3 }e1[maxn*2],e2[maxn*2];
4 inline void add1(int from,int to){
5 e1[&＃43;&＃43;cnt1].to&＃61;to;e1[cnt1].nxt&＃61;h1[from];h1[from]&＃61;cnt1;
6 }
7 inline void add2(int from,int to){
8 e2[&＃43;&＃43;cnt2].to&＃61;to;e2[cnt2].nxt&＃61;h2[from];h2[from]&＃61;cnt2;
9 }
10 int b1[maxn*2],b2[maxn*2],js[maxn],dis[maxn];
11 int s[maxn],l[maxn],t[maxn],ans[maxn];
12 void dfs2(int x){
13 int t1&＃61;b1[w[x]&＃43;deep[x]],t2&＃61;b2[w[x]-deep[x]&＃43;maxn];
14 //递归前先读桶里的数值&＃xff0c;t1是上行桶里的值&＃xff0c;t2是下行桶的值
15 for(int i&＃61;head[x];i;i&＃61;e[i].nxt){ //递归子树
16 int y&＃61;e[i].to;
17 if(y&＃61;&＃61;fa[x][0])continue;
18 dfs2(y);
19 }
20 b1[deep[x]]&＃43;&＃61;js[x];
21 //上行过程中&＃xff0c;当前点作为路径起点产生贡献&＃xff0c;入桶
22 for(int i&＃61;h1[x];i;i&＃61;e1[i].nxt){
23 //下行过程中&＃xff0c;当前点作为路径终点产生贡献&＃xff0c;入桶
24 int y&＃61;e1[i].to;
25 b2[dis[y]-deep[t[y]]&＃43;maxn]&＃43;&＃43;;
26 }
27 ans[x]&＃43;&＃61;b1[w[x]&＃43;deep[x]]-t1&＃43;b2[w[x]-deep[x]&＃43;maxn]-t2;
28 //计算上、下行桶内差值&＃xff0c;累加到ans[x]里面
29 for(int i&＃61;h2[x];i;i&＃61;e2[i].nxt){
30 //回溯前清除以此结点为LCA的起点和终点在桶内产生的贡献&＃xff0c;它们已经无效了
31 int y&＃61;e2[i].to;
32 b1[deep[s[y]]]--;
33 b2[dis[y]-deep[t[y]]&＃43;maxn]--;
34 }
35 }
36 int main(){
37 for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;){
38 s[i]&＃61;read();t[i]&＃61;read();
39 int lcaa&＃61;lca(s[i],t[i]); //求LCA
40 dis[i]&＃61;deep[s[i]]&＃43;deep[t[i]]-2*deep[lcaa];
41 js[s[i]]&＃43;&＃43;;//统计以s[i]为起点路径的条数
42 add1(t[i],i);//第i条路径加入到以t[i]为终点的路径集合中
43 add2(lcaa,i);//把每条路径归到对应的LCA集合中
44 if(deep[lcaa]&＃43;w[lcaa]&＃61;&＃61;deep[s[i]]){
45 //如果路径起点或终点刚好为LCA且LCA处是可观察到运动员的,答案--
46 ans[lcaa]--;
47 }
48 }
49 dfs2(1);
50 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){
51 printf("%lld ",ans[i]);
52 }
53 return 0;
54 }
完整高清无注释code
1 #include
2 using namespace std;
3 namespace gengyf{
4 #define ll long long
5 #define int long long
6 const int maxn&＃61;3e5&＃43;10;
7 inline int read(){
8 int x&＃61;0,f&＃61;1;
9 char c&＃61;getchar();
10 while(c<&＃39;0&＃39;||c>&＃39;9&＃39;){if(c&＃61;&＃61;&＃39;-&＃39;)f&＃61;-1;c&＃61;getchar();}
11 while(c>&＃61;&＃39;0&＃39;&&c<&＃61;&＃39;9&＃39;){x&＃61;(x*10)&＃43;c-&＃39;0&＃39;;c&＃61;getchar();}
12 return x*f;
13 }
14 int n,m,cnt,deep[maxn],fa[maxn][25],w[maxn],head[maxn];
15 int h1[maxn],h2[maxn],cnt1,cnt2;
16 struct edge{
17 int nxt,to;
18 }e[maxn*2],e1[maxn*2],e2[maxn*2];
19 inline void add(int from,int to){
20 e[&＃43;&＃43;cnt].to&＃61;to;e[cnt].nxt&＃61;head[from];head[from]&＃61;cnt;
21 }
22 inline void add1(int from,int to){
23 e1[&＃43;&＃43;cnt1].to&＃61;to;e1[cnt1].nxt&＃61;h1[from];h1[from]&＃61;cnt1;
24 }
25 inline void add2(int from,int to){
26 e2[&＃43;&＃43;cnt2].to&＃61;to;e2[cnt2].nxt&＃61;h2[from];h2[from]&＃61;cnt2;
27 }
28 void dfs1(int x){
29 for(int i&＃61;1;(1<
30 fa[x][i]&＃61;fa[fa[x][i-1]][i-1];
31 }
32 for(int i&＃61;head[x];i;i&＃61;e[i].nxt){
33 int y&＃61;e[i].to;
34 if(y&＃61;&＃61;fa[x][0])continue;
35 fa[y][0]&＃61;x;
36 deep[y]&＃61;deep[x]&＃43;1;
37 dfs1(y);
38 }
39 }
40 int lca(int x,int y){
41 if(x&＃61;&＃61;y)return x;
42 if(deep[x]<deep[y])swap(x,y);
43 int k&＃61;log(deep[x]-deep[y])/log(2);
44 for(int i&＃61;k;i>&＃61;0;i--){
45 if(deep[fa[x][i]]>&＃61;deep[y]){
46 x&＃61;fa[x][i];
47 }
48 if(x&＃61;&＃61;y)return x;
49 }
50 k&＃61;log(deep[x])/log(2);
51 for(int i&＃61;k;i>&＃61;0;i--){
52 if(fa[x][i]!&＃61;fa[y][i]){
53 x&＃61;fa[x][i];y&＃61;fa[y][i];
54 }
55 }
56 return fa[x][0];
57 }
58 int b1[maxn*2],b2[maxn*2],js[maxn],dis[maxn];
59 int s[maxn],l[maxn],t[maxn],ans[maxn];
60 void dfs2(int x){
61 int t1&＃61;b1[w[x]&＃43;deep[x]],t2&＃61;b2[w[x]-deep[x]&＃43;maxn];
62 for(int i&＃61;head[x];i;i&＃61;e[i].nxt){
63 int y&＃61;e[i].to;
64 if(y&＃61;&＃61;fa[x][0])continue;
65 dfs2(y);
66 }
67 b1[deep[x]]&＃43;&＃61;js[x];
68 for(int i&＃61;h1[x];i;i&＃61;e1[i].nxt){
69 int y&＃61;e1[i].to;
70 b2[dis[y]-deep[t[y]]&＃43;maxn]&＃43;&＃43;;
71 }
72 ans[x]&＃43;&＃61;b1[w[x]&＃43;deep[x]]-t1&＃43;b2[w[x]-deep[x]&＃43;maxn]-t2;
73 for(int i&＃61;h2[x];i;i&＃61;e2[i].nxt){
74 int y&＃61;e2[i].to;
75 b1[deep[s[y]]]--;
76 b2[dis[y]-deep[t[y]]&＃43;maxn]--;
77 }
78 }
79 int main(){
80 n&＃61;read();m&＃61;read();
81 for(int i&＃61;1;i
82 int u,v;u&＃61;read();v&＃61;read();
83 add(u,v);add(v,u);
84 }
85 deep[1]&＃61;1;fa[1][0]&＃61;1;dfs1(1);
86 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){
87 w[i]&＃61;read();
88 }
89 for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;){
90 s[i]&＃61;read();t[i]&＃61;read();
91 int lcaa&＃61;lca(s[i],t[i]);
92 dis[i]&＃61;deep[s[i]]&＃43;deep[t[i]]-2*deep[lcaa];
93 js[s[i]]&＃43;&＃43;;
94 add1(t[i],i);add2(lcaa,i);
95 if(deep[lcaa]&＃43;w[lcaa]&＃61;&＃61;deep[s[i]]){
96 ans[lcaa]--;
97 }
98 }
99 dfs2(1);
100 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){
101 printf("%lld ",ans[i]);
102 }
103 return 0;
104 }
105 }
106 signed main(){
107 gengyf::main();
108 return 0;
109 }
完结撒花花
京公网安备 11010802041100号