2019ICPC 上海现场赛补题

  1 #include<bits/stdc++.h>
  2 /*
  3 #include<cstdio>
  4 #include<cmath>
  5 #include<cstring>
  6 #include<vector>
  7 #include<cctype>
  8 #include<queue>
  9 #include<algorithm>
 10 #include<map>
 11 #include<set>
 12 */
 13 #pragma GCC optimize(2)
 14 using namespace std;
 15 typedef long long LL;
 16 typedef pair<int,int> pii;
 17 typedef pair<double,double> pdd;
 18 const int N=2e5+5;
 19 const int M=3005;
 20 const int inf=0x3f3f3f3f;
 21 const LL mod=1e9+7;
 22 const double eps=1e-9;
 23 const long double pi=acos(-1.0L);
 24 #define ls (i<<1)
 25 #define rs (i<<1|1)
 26 #define fi first
 27 #define se second
 28 #define pb push_back
 29 #define mk make_pair
 30 #define mem(a,b) memset(a,b,sizeof(a))
 31 LL read()
 32 {
 33     LL x=0,t=1;
 34     char ch;
 35     while(!isdigit(ch=getchar())) if(ch==‘-‘) t=-1;
 36     while(isdigit(ch)){ x=10*x+ch-‘0‘; ch=getchar(); }
 37     return x*t;
 38 }
 39 LL lazy1[N<<2],lazy2[N<<2];
 40 int deep[N],id[N],top[N],f[N],cnt[N],son[N],tot,n,m,a[N],rk[N];
 41 vector<int> e[N];
 42 struct node{ LL x,y,z; }c[N<<2];
 43 void dfs(int u,int pre)
 44 {
 45     f[u]=pre;
 46     cnt[u]=1;
 47     deep[u]=deep[pre]+1;
 48     for(auto v:e[u])
 49     {
 50         if(v==pre) continue;
 51         dfs(v,u);
 52         cnt[u]+=cnt[v];
 53         if(cnt[son[u]]<cnt[v]) son[u]=v;
 54     }
 55 }
 56 void dfs2(int u,int pre,int t)
 57 {
 58     top[u]=t;
 59     id[u]=++tot;
 60     rk[tot]=u;
 61     if(son[u]) dfs2(son[u],u,t);
 62     for(auto v:e[u])
 63         if(v!=son[u]&&v!=pre) dfs2(v,u,v);
 64 }
 65 inline LL s2(LL x)
 66 {
 67     return x*x%mod;
 68 }
 69 inline LL s3(LL x)
 70 {
 71     return x*x%mod*x%mod;
 72 }
 73 void calmul(int i,LL w)
 74 {
 75     c[i].x=c[i].x*w%mod;
 76     c[i].y=c[i].y*s2(w)%mod;
 77     c[i].z=c[i].z*s3(w)%mod;
 78     lazy1[i]=lazy1[i]*w%mod;
 79     lazy2[i]=lazy2[i]*w%mod;
 80 }
 81 void caladd(int i,LL len,LL w)
 82 {
 83     c[i].z=(c[i].z+len*s3(w)%mod+3LL*s2(w)%mod*c[i].x+3LL*w%mod*c[i].y%mod )%mod;
 84     c[i].y=(c[i].y+len*s2(w)%mod+2LL*w%mod*c[i].x%mod )%mod;
 85     c[i].x=(c[i].x+len*w%mod )%mod;
 86     lazy2[i]=(lazy2[i]+w)%mod;
 87 }
 88 void pushup(int i)
 89 {
 90     c[i].x=(c[ls].x+c[rs].x)%mod;
 91     c[i].y=(c[ls].y+c[rs].y)%mod;
 92     c[i].z=(c[ls].z+c[rs].z)%mod;
 93 }
 94 void pushdown(int i,int l,int r)
 95 {
 96     int mid=l+r>>1;
 97     calmul(ls,lazy1[i]);
 98     calmul(rs,lazy1[i]);
 99     caladd(ls,mid-l+1,lazy2[i]);
100     caladd(rs,r-mid,lazy2[i]);
101     lazy1[i]=1;
102     lazy2[i]=0;
103 }
104 void build(int i,int l,int r)
105 {
106     lazy1[i]=1;
107     lazy2[i]=0;
108     if(l==r)
109     {
110         LL t=a[rk[l]];
111         c[i].x=t;
112         c[i].y=s2(t);
113         c[i].z=s3(t);
114         return ;
115     }
116     int mid=l+r>>1;
117     build(ls,l,mid);
118     build(rs,mid+1,r);
119     pushup(i);
120 }
121 void update(int i,int l,int r,int ll,int rr,int flag,LL w)
122 {
123     if(ll<=l&&r<=rr)
124     {
125         if(flag==1)
126         {
127             LL len=r-l+1;
128             lazy1[i]=0;
129             lazy2[i]=w;
130             c[i].x=w*len%mod;
131             c[i].y=s2(w)*len%mod;
132             c[i].z=s3(w)*len%mod;
133         }
134         else if(flag==2) caladd(i,r-l+1,w);
135         else calmul(i,w);
136         return ;
137     }
138     pushdown(i,l,r);
139     int mid=l+r>>1;
140     if(mid>=ll) update(ls,l,mid,ll,rr,flag,w);
141     if(mid<rr) update(rs,mid+1,r,ll,rr,flag,w);
142     pushup(i);
143 }
144 LL query(int i,int l,int r,int ll,int rr)
145 {
146     if(ll<=l&&r<=rr) return c[i].z;
147     pushdown(i,l,r);
148     LL t1=0,t2=0;
149     int mid=l+r>>1;
150     if(mid>=ll) t1=query(ls,l,mid,ll,rr);
151     if(mid<rr) t2=query(rs,mid+1,r,ll,rr);
152     return (t1+t2)%mod;
153 }
154 void change(int x,int y,int flag,LL w)
155 {
156     while(top[x]!=top[y])
157     {
158         if(deep[top[x]]<deep[top[y]]) swap(x,y);
159         update(1,1,n,id[top[x]],id[x],flag,w);
160         x=f[top[x]];
161     }
162     if(id[x]>id[y]) swap(x,y);
163     update(1,1,n,id[x],id[y],flag,w);
164 }
165 LL getans(int x,int y)
166 {
167     LL ans=0;
168     while(top[x]!=top[y])
169     {
170         if(deep[top[x]]<deep[top[y]]) swap(x,y);
171         ans+=query(1,1,n,id[top[x]],id[x]);
172         ans%=mod;
173         x=f[top[x]];
174     }
175     if(id[x]>id[y]) swap(x,y);
176     ans+=query(1,1,n,id[x],id[y]);
177     ans%=mod;
178     return ans;
179 }
180 inline void init()
181 {
182     tot=0;
183     mem(son,0);
184     for(int i=1;i<=n;i++) e[i].clear();
185 }
186 int main()
187 {
188     int T=read(),test=0;
189     while(T--)
190     {
191         n=read();
192         for(int i=1;i<n;i++)
193         {
194             int x=read(),y=read();
195             e[x].pb(y);
196             e[y].pb(x);
197         }
198         for(int i=1;i<=n;i++) a[i]=read();
199         dfs(1,0);
200         dfs2(1,0,1);
201         build(1,1,n);
202         m=read();
203         printf("Case #%d:\n",++test);
204         while(m--)
205         {
206             int cmd=read(),u=read(),v=read();
207             if(cmd==4) printf("%lld\n",getans(u,v));
208             else
209             {
210                 LL w=read();
211                 change(u,v,cmd,w);
212             }
213         }
214         init();
215     }
216     return 0;
217 }