2019.10.10口胡题

D1T1

维护儿子和孙子异或和,每次改x只改x的父亲和爷爷,复杂度度O(n),以后口胡题尽量还是不要写正解+暴力+数据生成+对拍了,到最后题都没时间看完

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 #include
 7 #define int long long
 8 using namespace std;
 9 const int N=1e6+10,mod=1e9+7;
10 int sum,tot,n,m,s[N],g[N],a[N],f[N],head[N],to[N*2],ne[N*2]; //s:2 g:1
11 inline int read()
12 {
13         register int sum,k=1;register char s;
14         while(s=getchar(),s<'0'||s>'9') if(s=='-') k=-1;sum=s-'0';
15         while(s=getchar(),s>='0'&&s<='9') sum=sum*10+s-'0';
16         return k*sum;
17 }
18 void add(int x,int y)
19 {
20         to[++tot]=y;
21         ne[tot]=head[x];
22         head[x]=tot;
23 }
24 void dfs(int x,int fa)
25 {
26         f[x]=fa;
27         for(int i=head[x];i;i=ne[i])
28         {
29                 int y=to[i];
30                 if(y==fa) continue;
31                 g[x]^=a[y];
32                 if(fa) s[fa]^=a[y];
33                 dfs(y,x);
34         }
35 }
36 signed main()
37 {
38         freopen("1.in","r",stdin);
39         freopen("1.out","w",stdout);
40         n=read(),m=read();
41         for(int i=1;i<=n;i++) a[i]=read();
42         for(int i=1,x,y;i)
43         {
44                 x=read(),y=read();
45                 add(x,y),add(y,x);
46         }
47         dfs(1,0);
48         for(int i=1,x,y,cnt;i<=m;i++)
49         {
50                 x=read(),y=read();
51                 if(f[x]) g[f[x]]^=a[x]^y;
52                 if(f[f[x]]) s[f[f[x]]]^=a[x]^y;
53                 a[x]=y;
54                 cnt=a[x]^s[x]^g[x]^a[f[x]]^a[f[f[x]]];
55                 if(f[x]) cnt^=g[f[x]]^a[x];
56                 sum=(sum+(i*i%mod)*cnt%mod)%mod;
57         }
58         printf("%lld",sum);
59         return 0;
60 }
T1

 D1T2

听LNC口胡效果不错

 D1T3

咕咕

D2T1

考虑树的部分分,我们发现一定是所以负边权之和,因为叶子节点只有一个度,根据流量守恒,流量一定为零,推得所有边都为零,贪心地把所有负边权观察了就好。

对于环也一样,搞一发最小生成森林即可

D2T2T3

详见题解

 

你可能感兴趣的