QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#820449#4600. GilneasSGColinAC ✓1173ms35760kbC++203.0kb2024-12-18 21:28:532024-12-18 21:28:53

Judging History

This is the latest submission verdict.

  • [2024-12-18 21:28:53]
  • Judged
  • Verdict: AC
  • Time: 1173ms
  • Memory: 35760kb
  • [2024-12-18 21:28:53]
  • Submitted

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