QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#820449 | #4600. Gilneas | SGColin | AC ✓ | 1173ms | 35760kb | C++20 | 3.0kb | 2024-12-18 21:28:53 | 2024-12-18 21:28:53 |
Judging History
answer
#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const int maxn=200000,maxt=maxn<<2,MOD=1e9+7;
int te,n,m,si[maxn+5],SH[maxn+5],top[maxn+5];
int fa[maxn+5],lt[maxn+5],rt[maxn+5];
int E,lnk[maxn+5],nxt[maxn+5],to[maxn+5];
int len[maxt+5],sum[maxt+5],tag[maxt+5][2];
#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
static char buf[100000],*l=buf,*r=buf;
return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
T tot=0;char ch=readc(),lst='+';
while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
struct fastO{
int si;char buf[100000];
fastO() {si=0;}
void putc(char ch){
if (si==100000) fwrite(buf,1,si,stdout),si=0;
buf[si++]=ch;
}
~fastO() {fwrite(buf,1,si,stdout);}
}fo;
template<typename T> void writei(T x,char ch='\n'){
int len=0,buf[100];
if (x<0) fo.putc('-'),x=-x;
do buf[len++]=x%10,x/=10; while (x);
while (len) fo.putc(buf[--len]+48);
fo.putc(ch);
}
inline void Add(int x,int y) {to[++E]=y;nxt[E]=lnk[x];lnk[x]=E;}
void DFS(int x){
si[x]=1;SH[x]=0;
for (int j=lnk[x];j;j=nxt[j]){
DFS(to[j]);si[x]+=si[to[j]];
if (si[to[j]]>si[SH[x]]) SH[x]=to[j];
}
}
void HLD(int x,int lst){
lt[x]=++lt[0];top[x]=lst;
if (SH[x]) HLD(SH[x],lst);
for (int j=lnk[x];j;j=nxt[j])
if (to[j]!=SH[x]) HLD(to[j],to[j]);
rt[x]=lt[0];
}
void Build(int L,int R,int p=1){
len[p]=R-L+1;sum[p]=0;tag[p][0]=0;tag[p][1]=1;
if (L==R) return;
int mid=L+(R-L>>1);
Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);
}
inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;}
inline int MUL(int x,int y) {return (LL)x*y%MOD;}
void Addtag(int tp,int p,int k){
if (tp==1){
sum[p]=MUL(sum[p],k);
tag[p][1]=MUL(tag[p][1],k);
tag[p][0]=MUL(tag[p][0],k);
} else {
sum[p]=ADD(sum[p],MUL(len[p],k));
tag[p][0]=ADD(tag[p][0],k);
}
}
void Pushdown(int p){
if (tag[p][1]>1) Addtag(1,p<<1,tag[p][1]),Addtag(1,p<<1|1,tag[p][1]),tag[p][1]=1;
if (tag[p][0]>0) Addtag(0,p<<1,tag[p][0]),Addtag(0,p<<1|1,tag[p][0]),tag[p][0]=0;
}
void Insert(int tp,int L,int R,int k,int l=1,int r=n,int p=1){
if (L==l && r==R) return Addtag(tp,p,k);
int mid=l+(r-l>>1);Pushdown(p);
if (R<=mid) Insert(tp,L,R,k,l,mid,p<<1); else if (L>mid) Insert(tp,L,R,k,mid+1,r,p<<1|1);
else Insert(tp,L,mid,k,l,mid,p<<1),Insert(tp,mid+1,R,k,mid+1,r,p<<1|1);
sum[p]=ADD(sum[p<<1],sum[p<<1|1]);
}
void Update(int tp,int x,int k){
while (x){
Insert(tp,lt[top[x]],lt[x],k);
x=fa[top[x]];
}
}
int main(){
for (readi(te);te;te--){
readi(n);readi(m);
E=0;for (int i=1;i<=n;i++) lnk[i]=0;
for (int i=2;i<=n;i++) readi(fa[i]),Add(fa[i],i);
DFS(1);lt[0]=0;HLD(1,1);Build(1,n);
for (int i=1,x,c,p;i<=m;i++){
readi(x);readi(c);readi(p);
Update(1,x,(MOD+1-p)%MOD);
Update(0,fa[x],MUL(c,p));
}
writei(sum[1]);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1173ms
memory: 35760kb
input:
4 200000 200000 1 2 2 1 5 5 6 7 8 5 8 6 12 14 2 12 4 9 2 17 10 19 16 10 18 7 7 13 28 6 23 31 21 13 15 5 27 4 32 15 4 40 19 18 34 19 8 32 30 19 48 33 15 34 18 36 3 56 36 59 56 60 15 51 29 11 63 35 14 39 41 46 50 70 71 75 69 58 62 29 28 78 15 47 57 59 8 73 48 29 19 56 75 44 28 35 17 25 61 42 87 6 5 19...
output:
706075944 925415091 656041388 241292250
result:
ok 4 lines