Nowcoder练习赛26 E 树上路径

2018-09-07 21:09:15

• 子树加上一个值

• 路径加上一个值

• 询问一条路径上任取两个数的乘积的总和

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
typedef long long ll;
const int N=1e5+5,mod=1e9+7,inv2=5e8+4;
struct node
{
int to,nxt;
}edge[N<<1];
int cnt,idx[N],top[N],a[N],w[N];
ll sum1[N<<2],sum2[N<<2],tag[N<<2];
{
int x=0,w=1;
char c=getchar();
while (!isdigit(c)&&c!='-') c=getchar();
if (c=='-') c=getchar(),w=-1;
while (isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*w;
}
{
}
void dfs(int k,int father,int deep)
{
int bigson=0;
fa[k]=father; dep[k]=deep; tot[k]=1;
{
int v=edge[i].to;
if (v==father) continue;
dfs(v,k,deep+1); tot[k]+=tot[v];
if (bigson<tot[v]) bigson=tot[v],son[k]=v;
}
}
void dfs(int k,int tp)
{
idx[k]=++cnt; top[k]=tp; a[cnt]=k;
if (!son[k]) return; dfs(son[k],tp);
{
int v=edge[i].to;
if (!idx[v]) dfs(v,v);
}
}
inline void pushup(int now)
{
sum1[now]=(sum1[now<<1]+sum1[now<<1|1])%mod;
sum2[now]=(sum2[now<<1]+sum2[now<<1|1])%mod;
}
inline void pushdown(int now,int l,int r)
{
if (!tag[now]) return;
tag[now<<1]=(tag[now<<1]+tag[now])%mod; tag[now<<1|1]=(tag[now<<1|1]+tag[now])%mod;
sum2[now<<1]=(sum2[now<<1]+1ll*tag[now]*tag[now]*l+2ll*tag[now]*sum1[now<<1])%mod;
sum2[now<<1|1]=(sum2[now<<1|1]+1ll*tag[now]*tag[now]*r+2ll*tag[now]*sum1[now<<1|1])%mod;
sum1[now<<1]=(sum1[now<<1]+1ll*tag[now]*l)%mod; sum1[now<<1|1]=(sum1[now<<1|1]+1ll*tag[now]*r)%mod;
tag[now]=0;
}
void build(int l,int r,int now)
{
if (l==r)
{
sum1[now]=1ll*w[a[l]]%mod;
sum2[now]=1ll*w[a[l]]*w[a[l]]%mod;
return;
}
int mid=(l+r)>>1;
build(l,mid,now<<1);
build(mid+1,r,now<<1|1);
pushup(now);
}
void inchange(int L,int R,int l,int r,int now,int c)
{
if (l>R||r<L) return;
if (l>=L&&r<=R)
{
sum2[now]=(sum2[now]+1ll*c*c*(r-l+1)+2ll*c*sum1[now])%mod;
sum1[now]=(sum1[now]+1ll*c*(r-l+1))%mod; tag[now]=(tag[now]+c)%mod; return;
}
int mid=(l+r)>>1; pushdown(now,mid-l+1,r-mid);
if (mid>=R) inchange(L,R,l,mid,now<<1,c);
else if (mid<L) inchange(L,R,mid+1,r,now<<1|1,c);
else
{
inchange(L,mid,l,mid,now<<1,c);
inchange(mid+1,R,mid+1,r,now<<1|1,c);
}
pushup(now);
}
ll ingetsum1(int L,int R,int l,int r,int now)
{
if (l>R||r<L) return 0;
if (l>=L&&r<=R) return sum1[now]%mod;
int mid=(l+r)>>1; pushdown(now,mid-l+1,r-mid);
if (mid>=R) return ingetsum1(L,R,l,mid,now<<1);
if (mid<L) return ingetsum1(L,R,mid+1,r,now<<1|1);
return (ingetsum1(L,mid,l,mid,now<<1)+ingetsum1(mid+1,R,mid+1,r,now<<1|1))%mod;
}
ll ingetsum2(int L,int R,int l,int r,int now)
{
if (l>R||r<L) return 0;
if (l>=L&&r<=R) return sum2[now]%mod;
int mid=(l+r)>>1; pushdown(now,mid-l+1,r-mid);
if (mid>=R) return ingetsum2(L,R,l,mid,now<<1);
if (mid<L) return ingetsum2(L,R,mid+1,r,now<<1|1);
return (ingetsum2(L,mid,l,mid,now<<1)+ingetsum2(mid+1,R,mid+1,r,now<<1|1))%mod;
}
inline void treechange(int x,int y,int val)
{
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
inchange(idx[top[x]],idx[x],1,n,1,val);
x=fa[top[x]];
}
if (dep[x]>dep[y]) swap(x,y);
inchange(idx[x],idx[y],1,n,1,val);
}
inline ll treesum1(int x,int y)
{
ll ans=0;
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
ans=(ans+ingetsum1(idx[top[x]],idx[x],1,n,1))%mod;
x=fa[top[x]];
}
if (dep[x]>dep[y]) swap(x,y);
ans=(ans+ingetsum1(idx[x],idx[y],1,n,1))%mod;
return ans;
}
inline ll treesum2(int x,int y)
{
ll ans=0;
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
ans=(ans+ingetsum2(idx[top[x]],idx[x],1,n,1))%mod;
x=fa[top[x]];
}
if (dep[x]>dep[y]) swap(x,y);
ans=(ans+ingetsum2(idx[x],idx[y],1,n,1))%mod;
return ans;
}
int main()
{
for (reg int i=1;i<n;i++)
{
}
dfs(1,0,1); dfs(1,1); build(1,n,1);
while (m--)
{
}