多校联测20191009test

题目：

1 文体两开花
1.1题目描述
众所周知，小G擅长文体两开花。 现在小G手中拿到了一棵树，这棵树的每个节点上都有一个非负整数权值vali。 为了展现自己深不可测的开花功底，小G会对这棵树进行一系列操作，具体表现为修改某个节点x
的权值。在每次修改之后，小G想要你告诉他，所有与节点x距离不超过2的所有节点的权值异或和是
多少。
1.2输入格式
从文件blossom.in中读入数据。 输入数据第一行包含两个正整数n,q，表示树的节点数以及修改/询问次数。
第一行n个空格隔开的正整数vali，表示每个点的权值。
接下来n~1行，每行两个正整数x,y，表示一条树边(x,y)。
接下来q行，每行两个整数x,v，表示将节点x的权值修改成v。
1.3输出格式
输出到文件blossom.out中。
为避免输出过量，记第i次询问的答案为ansi，你只需要输出∑(q)i=1ansi×i2对109+7取模的结果即可。
1.4样例1输入
5 3
1 2 3 4 5
1 2
1 3
2 4
2 5
3 6
4 7
5 8
1.5样例1输出
117
1.6样例1解释
3次询问对应的答案分别为5,1,12。
对于30%的数据，1≤n,q≤1000。
对于60%的数据，1≤n,q≤105。
对于100%的数据，1≤n,q≤106,1≤x,y≤n,0≤vali,v<230。
 
sol
模拟即可：
注意直接预处理出距离为2以内的异或值，改变的时候全部改一下即可
时间复杂度O（n+q）
code：
 

1 #include
2 #pragma GCC optmize(3)
3 #define int long long
4 using namespace std;
5 int ans;
6 int n,q;
7 inline int read(){
8 int x=0,f=1;char ch=getchar();
9 while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
10 while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
11 return x*f;
12 }
13 const int N=1001000,mod=1e9+7;
14 int to[N*2],head[N],Next[N*2],dep1[N],dep2[N],a[N],fa[N];
15 int cnt=0;
16 void add(int x,int y){to[++cnt]=y;Next[cnt]=head[x];head[x]=cnt;}
17 void dfs(int x,int ffa)
18 {
19 dep1[fa[x]]^=a[x];//预处理出与 x 同一距离根节点为1的异或值
20 dep2[fa[ffa]]^=a[x];//预处理出与 ffa 同一距离根节点为1的异或值
21 for (int i=head[x];i;i=Next[i])
22 {
23 int u=to[i];
24 if (u==ffa) continue;
25 fa[u]=x;//u 的父亲为 x
26 dfs(u,x);
27 }
28 //cout<<"dep1[fa[x]]= "<33 //freopen("blossom.out","w",stdout);
34
35 n=read();q=read();
36 for (int i=1;i<=n;i++) a[i]=read();
37 for (int i=1;i38 {
39 int x,y;
40 x=read();
41 y=read();
42 add(x,y);add(y,x);
43 }
44 dfs(1,0);
45 for (int i=1;i<=q;i++)
46 {
47 int x,v;
48 x=read();v=read();
49 //cout<<"dep1[fa[x]]= "<63 return 0;
64 }
65 /*
66 5 3
67 1 2 3 4 5
68 1 2
69 1 3
70 2 4
71 2 5
72 3 6
73 4 7
74 5 8
75
76 */

但以上代码只有60分，会T掉4个点，如果你把快读改成一个更优的话，AC100

 如下快读

1 inline char read() {
2 static const int IN_LEN = 1000000;
3 static char buf[IN_LEN], *s, *t;
4 return (s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin), (s == t ? -1 : *s++) : *s++);
5 }
6 template
7 inline void read(T &x) {
8 static bool iosig;
9 static char c;
10 for (iosig = false, c = read(); !isdigit(c); c = read()) {
11 if (c == '-') iosig = true;
12 if (c == -1) return;
13 }
14 for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
15 if (iosig) x = -x;
16 }

 

考场上我是直接暴力枚举，使用了换根法，导致每次都跑了一遍dfs，一共q次，再加上O(n*q)的暴力枚举

导致我只拿了30分，其余全部TLE了，考场SB代码：

code：

 

1 #include
2 #pragma GCC optimize(3)
3 #define int long long
4 const int mod=1e9+7;
5 const int N=1e6+10;
6 using namespace std;
7 int yzl;
8 int n,q,w,cnt,fuck,vv;
9 int a[N];
10 int tot,ver[N],head[N],nxt[N];
11 int dep[N],depp[N],ans[N];
12 void inint(){
13 freopen("blossom.in","r",stdin);
14 freopen("blossom.out","w",stdout);
15 }
16 inline int read(){
17 int x=0,f=1;char ch=getchar();
18 while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
19 while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
20 return x*f;
21 }
22 void add(int x,int y){
23 ++tot;
24 ver[tot]=y;
25 nxt[tot]=head[x];
26 head[x]=tot;
27 }
28 void dfs(int x,int fa){
29 // dep[x]=0;
30 depp[x]=depp[fa]+1;
31 for(int i=head[x];i;i=nxt[i]){
32 int y=ver[i];
33 if(y!=fa){
34 // dep[y]=dep[x]+1;
35 dfs(y,x);
36 depp[y]=depp[x]+1;
37 //cout<<"dep= "< 38 }
39 }
40 }
41 void dfs2(int x,int fa){
42 dep[x]=dep[fa]+1;
43 for(int i=head[x];i;i=nxt[i]){
44 int y=ver[i];
45 if(y!=fa){
46
47 dfs2(y,x);
48 w=x;
49 dep[y]=dep[x]+1;
50 // cout<<"x= "<110 return 0;
111 }
112 /*
113 5 3
114 1 2 3 4 5
115 1 2
116 1 3
117 2 4
118 2 5
119 3 6
120 4 7
121 5 8
122
123 117
124 */

 

心得总结：尽管我现在还是弱鸡一枚，连多校题只能开暴力(还是只有NOIP难度)，得分现在加起来连50都没有，但是原来我可能连暴力都打不满，经过2个月的训练，代码能力也逐渐提升了。

有些神犇大佬们不屑于做的题目但他们可能会掉意轻心，比如(一些小细节)，可能最后得分还不如最浅显的暴力。

最后还是那句话：只要坚持不懈，就一点会成功。无论结果如何，只要自己尽最大的努力，也不会有遗憾了。