noip模擬48
A. Lighthouse
很明顯的容斥題，組合式與上上場 \(t2\) 一模一樣
注意判環(huán)時(shí)長度為 \(n\) 的環(huán)是合法的
B. Miner
題意實(shí)際上是要求偶拉路
對(duì)于一個(gè)有多個(gè)奇數(shù)點(diǎn)的聯(lián)通塊，直接 \(dfs\) 是不對(duì)的，可能搜索是來的不是一條路徑
可以把個(gè)數(shù)大于 \(2\) 的聯(lián)通塊先強(qiáng)制奇數(shù)點(diǎn)兩兩連邊，再跑兩個(gè)奇數(shù)點(diǎn)的偶拉路
直接跑會(huì) \(t\)，可以加入類似當(dāng)前弧優(yōu)化，注意每次 \(dfs\) 回溯時(shí)也要更新邊為當(dāng)前弧
void dfs(int u){
for(int i=hd[u];i;){
hd[u]=edge[i].nxt;
if(!vis[i>>1]){
int v=edge[i].to;
deg[u]--;
deg[v]--;
vis[i>>1]=true;
dfs(v);
sta1[++tp1]=make_pair(edge[i].val,v);
i=hd[u];
}
else i=edge[i].nxt;
}
return ;
}
C. Lyk Love painting
這 \(m\) 幅畫居然不能重疊……
首先肯定二分，然后 \(dp\) 驗(yàn)證
設(shè) \(f[i][j]\) 表示第一行選到第 \(i\) 列總共選了 \(j\) 幅畫第二行最遠(yuǎn)選到第幾幅畫
轉(zhuǎn)移需要雙指針預(yù)處理第一行，第二行，以及兩行從每一列出發(fā)最遠(yuǎn)能到達(dá)的距離
D. Revive
先把平方拆開，分為兩部分：
- 對(duì)于每條邊，其平方計(jì)算了經(jīng)過這條邊的路徑數(shù)次，為 \(siz_u(n-siz_u)\)
- 對(duì)于每兩條邊，其乘機(jī)的二倍計(jì)算了同時(shí)經(jīng)過這兩條邊的路徑次數(shù)
可以分三類討論： - \(v\) 在 \(u\) 子樹內(nèi)，為 \(2(n-siz[u]) * val[u] * siz[v] * val[v]\)
- \(v\) 在 \(u\) 到根節(jié)點(diǎn)路徑上，為 \(2siz[u] * val[u] * (n-siz[v]) * val[v]\)
- \(v\) 和 \(u\) 的 \(lca\) 不是兩點(diǎn)中的任意一個(gè)，為 \(2siz[u] * val[u] * siz[v] * val[v]\)
發(fā)現(xiàn)和 \(v\) 有關(guān)的式子都是 \(siz[v] * val[v]\)，那么用線段樹維護(hù)這個(gè)值即可
由于需要維護(hù)到根節(jié)點(diǎn)路徑的值，可以另開一棵記錄每個(gè)點(diǎn)到根節(jié)點(diǎn)的前綴和，這樣轉(zhuǎn)化成每次區(qū)間修改單點(diǎn)查詢，避免了多次跳鏈的 \(log\)
子樹內(nèi)權(quán)值和可以用樹狀數(shù)組維護(hù)以卡常
代碼實(shí)現(xiàn)
#include<bits/stdc++.h>
using namespace std;
#define in long long
#define int long long
const int maxn=1e5+5;
const int maxm=1e5+5;
const int mod=1e9+7;
const int stan=1e15;
in n,m,fa[maxn],x,siz[maxn],re[maxn],dfn[maxn],hd[maxn],cnt,num;
int ans,w,val[maxn],sum[maxn],sum1[maxn],sumtot,c[maxn];
in read(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=getchar();
}
while(isdigit(ch)){
x=x*10+ch-48;
ch=getchar();
}
return x*f;
}
struct Edge{
in nxt,to;
}edge[maxm];
void add(in u,in v){
edge[++cnt].nxt=hd[u];
edge[cnt].to=v;
hd[u]=cnt;
return ;
}
void change1(int x,int w){
for(;x<=n;x+=x&-x)c[x]=(c[x]+w)%mod;
return ;
}
int ask3(int x){
int ans=0;
for(;x;x-=x&-x)ans=(ans+c[x])%mod;
return ans;
}
void modadd(int &x,int y){
x=(x+y)%mod;
if(x<0)x=(x+mod)%mod;
}
void dfs(in u){
siz[u]=1;
for(in i=hd[u];i;i=edge[i].nxt){
in v=edge[i].to;
dfs(v);
siz[u]+=siz[v];
}
return ;
}
void dfs1(in u){
sum[u]=(sum[fa[u]]+siz[u]*val[u]%mod)%mod;
sum1[u]=(sum1[fa[u]]+val[u])%mod;
// cout<<"ppp "<<sum1[u]<<endl;
dfn[u]=++num;
re[num]=u;
for(in i=hd[u];i;i=edge[i].nxt){
in v=edge[i].to;
dfs1(v);
}
return ;
}
struct Seg{
in l,r;
int sum,lazy,sum1,lazy1,sum2,lazy2;
}t[maxn*4];
void update(in p){
t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
t[p].sum1=t[p<<1].sum1+t[p<<1|1].sum1;
// if(t[p].sum>stan)t[p].sum%=mod;
// if(t[p].sum1>stan)t[p].sum1%=mod;
// t[p].sum2=t[p<<1].sum2+t[p<<1|1].sum2;
return ;
}
void build(in p,in l,in r){
t[p].l=l;
t[p].r=r;
if(l==r){
t[p].sum=sum[re[l]];
t[p].sum1=sum1[re[l]];
// t[p].sum2=siz[re[l]]*val[re[l]]%mod;
return ;
}
in mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
update(p);
return ;
}
void tospread(in p,int w1,int w2){
t[p].lazy=t[p].lazy+w1;
t[p].lazy1=t[p].lazy1+w2;
t[p].sum=t[p].sum+w1;
t[p].sum1=t[p].sum1+w2;
return ;
}
//void tospread1(in p,int w){
// t[p].lazy2=t[p].lazy2+w;
// t[p].sum2=t[p].sum2+w;
// return ;
//}
void spread(in p){
tospread(p<<1,t[p].lazy,t[p].lazy1);
tospread(p<<1|1,t[p].lazy,t[p].lazy1);
t[p].lazy=t[p].lazy1=0;
return ;
}
//void spread1(in p){
// tospread1(p<<1,t[p].lazy2);
// tospread1(p<<1|1,t[p].lazy2);
// t[p].lazy2=0;
// return ;
//}
void change(in p,in l,in r,int w1,int w2){
if(l>r)return ;
if(t[p].l>=l&&t[p].r<=r){
tospread(p,w1,w2);
return ;
}
if(t[p].lazy||t[p].lazy1)spread(p);
// if(t[p].lazy2)spread1(p);
in mid=t[p].l+t[p].r>>1;
if(l<=mid)change(p<<1,l,r,w1,w2);
if(r>mid)change(p<<1|1,l,r,w1,w2);
update(p);
return ;
}
//void change1(in p,in l,in r,int w){
// if(l>r)return ;
// if(t[p].l>=l&&t[p].r<=r){
// tospread1(p,w);
// return ;
// }
// if(t[p].lazy||t[p].lazy1)spread(p);
// if(t[p].lazy2)spread1(p);
// in mid=t[p].l+t[p].r>>1;
// if(l<=mid)change1(p<<1,l,r,w);
// if(r>mid)change1(p<<1|1,l,r,w);
// update(p);
// return ;
//}
int ask(in p,in l,in r){
// cout<<t[p].l<<" "<<t[p].r<<" "<<l<<" "<<r<<endl;
if(l>r)return 0;
if(t[p].l>=l&&t[p].r<=r)return t[p].sum;
int mid=t[p].l+t[p].r>>1,ans=0;
if(t[p].lazy||t[p].lazy1)spread(p);
// if(t[p].lazy2)spread1(p);
if(l<=mid)ans=ask(p<<1,l,r);
if(r>mid)ans=ans+ask(p<<1|1,l,r);
if(ans>stan)ans%=mod;
return ans;
}
int ask1(in p,in l,in r){
if(l>r)return 0;
if(t[p].l>=l&&t[p].r<=r)return t[p].sum1;
in mid=t[p].l+t[p].r>>1,ans=0;
if(t[p].lazy||t[p].lazy1)spread(p);
// if(t[p].lazy2)spread1(p);
if(l<=mid)ans=ask1(p<<1,l,r);
if(r>mid)ans=ans+ask1(p<<1|1,l,r);
if(ans>stan)ans%=mod;
return ans;
}
int ask2(in p,in l,in r){
if(l>r)return 0;
if(t[p].l>=l&&t[p].r<=r)return t[p].sum2;
in mid=t[p].l+t[p].r>>1,ans=0;
if(t[p].lazy||t[p].lazy1)spread(p);
// if(t[p].lazy2)spread1(p);
if(l<=mid)ans=ask2(p<<1,l,r);
if(r>mid)ans=ans+ask2(p<<1|1,l,r);
if(ans>stan)ans%=mod;
return ans;
}
int solve(in u,int w,in op){
int res=0;
int sumz=0;
if(siz[u]>1)sumz=ask3(dfn[u]+siz[u]-1)-ask3(dfn[u]);
// int sumz=ask2(1,dfn[u]+1,dfn[u]+siz[u]-1);
// cout<<"hhh "<<u<<" "<<sumz<<endl;
// cout<<ask(1,dfn[u]+1,dfn[u]+siz[u]-1)<<" "<<ask(1,dfn[u],dfn[u])<<endl;
//cout<<"hhh"<<endl;
int suml=ask(1,dfn[fa[u]],dfn[fa[u]])%mod;
// cout<<" "<<ask1(1,dfn[fa[u]],dfn[fa[u]])<<endl;
modadd(res,ask1(1,dfn[fa[u]],dfn[fa[u]])%mod*n%mod-suml);
// cout<<res<<endl;
// cout<<sumtot<<" "<<suml<<" "<<sumz<<endl;
modadd(res,sumtot-suml-siz[u]*val[u]%mod-sumz);
// cout<<res<<endl;
res=2*res*siz[u]%mod*w%mod;
// cout<<res<<endl;
modadd(res,2*w*(n-siz[u])%mod*sumz%mod);
// cout<<"hhh "<<res<<endl;
// cout<<res<<endl;
if(op){
change(1,dfn[u],dfn[u]+siz[u]-1,w*siz[u]%mod,w);
change1(dfn[u],w*siz[u]%mod);
// change1(1,dfn[u],dfn[u],w*siz[u]);
modadd(sumtot,w*siz[u]%mod);
}
return res;
}
int po(int a,int b=mod-2){
int ans=1;
while(b){
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
signed main(){
// freopen("revive3.in","r",stdin);
// freopen("shuju.in","r",stdin);
// freopen("my.out","w",stdout);
n=read();
n=read(),m=read();
for(int i=2;i<=n;i++){
fa[i]=read();
val[i]=read();
add(fa[i],i);
}
dfs(1);
dfs1(1);
build(1,1,n);
for(int i=1;i<=n;i++)change1(dfn[i],siz[i]*val[i]%mod);
for(int i=1;i<=n;i++)modadd(sumtot,val[i]*siz[i]%mod);
for(int i=2;i<=n;i++){
// cout<<"id: "<<i<<endl;
// cout<<solve(i,val[i],0)<<" ";
ans=(ans+solve(i,val[i],0))%mod;
}
ans=ans*po(2)%mod;
// cout<<ans<<endl;
for(int i=2;i<=n;i++){
ans=(ans+val[i]*val[i]%mod*siz[i]%mod*(n-siz[i])%mod)%mod;
}
cout<<ans<<endl;
for(int i=1;i<=m;i++){
x=read();
w=read();
ans=(ans-val[x]*val[x]%mod*siz[x]%mod*(n-siz[x])%mod)%mod;
ans=(ans+mod)%mod;
ans=(ans+solve(x,w,1))%mod;
val[x]+=w;
val[x]%=mod;
ans=(ans+val[x]*val[x]%mod*siz[x]%mod*(n-siz[x])%mod)%mod;
printf("%lld\n",ans);
}
return 0;
}
浙公網(wǎng)安備 33010602011771號(hào)