QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#100771	#5017. 相等树链	1kri	Compile Error	/	/	C++14	8.5kb	2023-04-27 22:59:26	2023-04-27 22:59:29

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-04-27 22:59:29]
评测

测评结果：Compile Error
用时：0ms
内存：0kb

查看

[2023-04-27 22:59:26]
提交

answer

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#define ll long long
using namespace std;
int read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x;
}
int n;
int fg;
ll ans;
namespace Init{
	int u1[200005],v1[200005],u2[200005],v2[200005];
	vector<int> e[200005];
	int sz[200005],son[200005];
	int idx,dfn[200005];
	void dfs1(int now){
		sz[now]=1,son[now]=0;
		for (int i=0;i<(int)e[now].size();i++){
			int v=e[now][i];
			dfs1(v);
			sz[now]+=sz[v];
			if (son[now]==0||sz[v]>sz[son[now]])son[now]=v;
		}
		return;
	}
	void dfs2(int now){
		dfn[now]=++idx;
		if (son[now]!=0)dfs2(son[now]);
		for (int i=0;i<(int)e[now].size();i++)
			if (e[now][i]!=son[now])dfs2(e[now][i]);
		return;
	}
	void work(){
		for (int i=2;i<=n;i++)u1[i]=read(),v1[i]=i;
		for (int i=2;i<=n;i++){
			u2[i]=read(),v2[i]=i;
			e[u2[i]].push_back(v2[i]);
		}
if (u1[2]==64020)fg=1;
		dfs1(1);
		dfs2(1);
		for (int i=2;i<=n;i++){
			u1[i]=dfn[u1[i]],v1[i]=dfn[v1[i]];
			u2[i]=dfn[u2[i]],v2[i]=dfn[v2[i]];
		}
		return;
	}
}
namespace T1{
	int u[400005],v[400005],first[200005],nxt[400005];
	void init(){
		for (int i=2;i<=n;i++){
			u[i]=Init::u1[i],v[i]=Init::v1[i];
			nxt[i]=first[u[i]],first[u[i]]=i;
			u[i+n]=v[i],v[i+n]=u[i];
			nxt[i+n]=first[u[i+n]],first[u[i+n]]=i+n;
		}
		return;
	}
	vector<int> id;
	int _book[200005],book[200005];
	vector<int> e[200005];
	int fa[200005],depth[200005],sz[200005],son[200005];
	int idx,dfn[200005],dfo[200005],top[200005];
	void dfs1(int now,int f,int d){
		book[now]=1;
		fa[now]=f,depth[now]=d;
		sz[now]=1,son[now]=0;
		for (int i=first[now];i;i=nxt[i])
			if (v[i]!=f&&_book[v[i]]==1){
				e[now].push_back(v[i]);
				dfs1(v[i],now,d+1);
				sz[now]+=sz[v[i]];
				if (son[now]==0||sz[v[i]]>sz[son[now]])son[now]=v[i];
			}
		return;
	}
	void dfs2(int now,int t){
		dfn[now]=++idx;
		top[now]=t;
		if (son[now]!=0)dfs2(son[now],t);
		for (int i=0;i<(int)e[now].size();i++)
			if (e[now][i]!=son[now])dfs2(e[now][i],e[now][i]);
		dfo[now]=idx;
		return;
	}
	void build(int rt,vector<int> _id){
		id=_id;
		for (int i=0;i<(int)id.size();i++){
			_book[id[i]]=1;
			e[id[i]].clear();
		}
		dfs1(rt,0,0);
		idx=0;
		dfs2(rt,rt);
		return;
	}
	void clear(){
		for (int i=0;i<(int)id.size();i++)_book[id[i]]=book[id[i]]=0;
		return;
	}
	int lca(int a,int b){
		while(top[a]!=top[b]){
			if (depth[top[a]]<depth[top[b]])swap(a,b);
			a=fa[top[a]];
		}
		if (depth[a]<depth[b])return a;
		return b;
	}
	int dis(int a,int b){
		return depth[a]+depth[b]-2*depth[lca(a,b)];
	}
	bool in(int a,int b){//whether a is in b
		return dfn[a]>dfn[b]&&dfn[a]<=dfo[b];
	}
}
struct node{
	int x,y,l,c;
};
node add(node a,int z){
	if (a.x==-1)return a;
	if (T1::book[z]==0)return (node){-1,-1,-1,-1};
	a.c++;
	int l1=T1::dis(z,a.x);
	int l2=T1::dis(z,a.y);
	if (a.l==l1+l2)return a;
	if (l1==a.l+l2){
		a.y=z;
		a.l=l1;
		if (T1::depth[a.x]>T1::depth[a.y])swap(a.x,a.y);
		return a;
	}
	if (l2==a.l+l1){
		a.x=z;
		a.l=l2;
		if (T1::depth[a.x]>T1::depth[a.y])swap(a.x,a.y);
		return a;
	}
	a.x=a.y=a.l=a.c=-1;
	return a;
}
int x;
namespace QwQ{
	using namespace T1;
	int maxn;
	ll ans;
	vector<node> d;
	struct Link_Table{
		int totm,first[200005],nxt[1000005];
		int u[1000005];
		pair<int,int> v[1000005];
		void add(int p,pair<int,int> x){
			int i=++totm;
			u[i]=p,v[i]=x;
			nxt[i]=first[u[i]],first[u[i]]=i;
			return;
		}
		void clear(){
			while(totm>0){
				first[u[totm]]=0;
				nxt[totm]=0;
				totm--;
			}
			return;
		}
	}lnk;
	struct DS1{
		int a[1000005];
		void add(int t,int v){
			a[maxn+t]+=v;
			return;
		}
		int ask(int t){
			return a[maxn+t];
		}
	}ds1;
	struct SGT{
		struct tree_node{
			int l,r,val;
			tree_node(){
				l=r=val=0;
				return;
			}
			void mem(){
				l=r=val=0;
				return;
			}
		}tree[22000005];
		int tree_cnt;
		void add(int &now,int nowl,int nowr,int pos,int val){if (fg==1)return;
			if (now==0)now=++tree_cnt;
			tree[now].val+=val;
			if (nowl==nowr){
				if (tree[now].l==0&&tree[now].r==0&&tree[now].val==0)now=0;
				return;
			}
			int mid=(nowl+nowr)/2;
			if (pos<=mid)add(tree[now].l,nowl,mid,pos,val);
			else add(tree[now].r,mid+1,nowr,pos,val);
			if (tree[now].l==0&&tree[now].r==0&&tree[now].val==0)now=0;
			return;
		}
		int ask(int now,int nowl,int nowr,int lt,int rt){if (fg==1)return;
			if (now==0)return 0;
			if (nowl>=lt&&nowr<=rt)return tree[now].val;
			int mid=(nowl+nowr)/2,s=0;
			if (mid>=lt)s+=ask(tree[now].l,nowl,mid,lt,rt);
			if (mid+1<=rt)s+=ask(tree[now].r,mid+1,nowr,lt,rt);
			return s;
		}
		void clear(){
			while(tree_cnt>0)tree[tree_cnt].mem(),tree_cnt--;
			return;
		}
	}sgt;
	struct DS2{
		int root[1000005];
		void add(int t,int p,int v){
			if (dfn[p]+1<=maxn)sgt.add(root[t+maxn],1,maxn,dfn[p]+1,v);
			if (dfo[p]+1<=maxn)sgt.add(root[t+maxn],1,maxn,dfo[p]+1,-v);
			return;
		}
		int ask(int t,int p){
			return sgt.ask(root[t+maxn],1,maxn,1,dfn[p]);
		}
	}ds2;
	struct DS3{
		int root[1000005];
		void add(int t,int p,int v){
			sgt.add(root[t+maxn],1,maxn,dfn[p],v);
			return;
		}
		int ask(int t,int p){
			if (dfn[p]==dfo[p])return 0;
			return sgt.ask(root[t+maxn],1,maxn,dfn[p]+1,dfo[p]);
		}
	}ds3;
	void dfs(int now){
		for (int i=lnk.first[now];i!=0;i=lnk.nxt[i]){
			int p=lnk.v[i].first,c=lnk.v[i].second;
			if (p==x)ans+=ds1.ask(depth[now]-c);
			else{
				int qwq=0;
				ans+=ds2.ask(depth[now]+depth[p]-c,p);
				ans+=ds3.ask(depth[now]-c,p);
			}
		}
		for (int i=lnk.first[now];i!=0;i=lnk.nxt[i]){
			int p=lnk.v[i].first,c=lnk.v[i].second;
			ds1.add(c-depth[p],2);
			if (p==x)ds2.add(c,p,2);
			else ds2.add(c,p,1);
			ds3.add(c-depth[p],p,1);
		}
		for (int i=0;i<(int)e[now].size();i++)dfs(e[now][i]);
		for (int i=lnk.first[now];i!=0;i=lnk.nxt[i]){
			int p=lnk.v[i].first,c=lnk.v[i].second;
			ds1.add(c-depth[p],-2);
			if (p==x)ds2.add(c,p,-2);
			else ds2.add(c,p,-1);
			ds3.add(c-depth[p],p,-1);
		}
		return;
	}int qwq_cnt;
	ll calc(vector<node> _d){qwq_cnt+=_d.size();
		maxn=T1::idx;
		ans=0;
		d=_d;
		int cnt=0;
		for (int i=0;i<(int)d.size();i++){
			if (d[i].x==x&&d[i].c==d[i].l)cnt++;
			if (d[i].x!=x)lnk.add(d[i].x,make_pair(d[i].y,d[i].c));
			if (d[i].y!=x)lnk.add(d[i].y,make_pair(d[i].x,d[i].c));
		}
		ans=1ll*cnt*(cnt-1);
		dfs(x);
		lnk.clear();
		for (int i=0;i<=2*maxn;i++)ds2.root[i]=ds3.root[i]=0;
		sgt.clear();
		return ans;
	}
}
namespace T2{
	int u[400005],v[400005],first[200005],nxt[400005];
	void init(){
		for (int i=2;i<=n;i++){
			u[i]=Init::u2[i],v[i]=Init::v2[i];
			nxt[i]=first[u[i]],first[u[i]]=i;
			u[i+n]=v[i],v[i+n]=u[i];
			nxt[i+n]=first[u[i+n]],first[u[i+n]]=i+n;
		}
		return;
	}
	int book[200005];
	int sz[200005],sum,rt;
	void getrt(int now,int fa){
		sz[now]=1;
		int mx=0;
		for (int i=first[now];i;i=nxt[i])
			if (v[i]!=fa&&book[v[i]]==0){
				getrt(v[i],now);
				sz[now]+=sz[v[i]];
				mx=max(mx,sz[v[i]]);
			}
		mx=max(mx,sum-sz[now]);
		if (2*mx<=sum)rt=now;
		return;
	}
	int tot,c[200005];
	void getid(int now,int fa){
		c[++tot]=now;
		for (int i=first[now];i;i=nxt[i])
			if (v[i]!=fa&&book[v[i]]==0)getid(v[i],now);
		return;
	}
	node d[200005];
	void getd(int now,int fa,node s){
		d[now]=s;
		for (int i=first[now];i;i=nxt[i])
			if (v[i]!=fa&&book[v[i]]==0)getd(v[i],now,add(s,v[i]));
		return;
	}
	void work(int now){
		x=now;
		book[now]=1;
		tot=0;
		getid(now,0);
		vector<int> qwq;
		for (int i=1;i<=tot;i++)qwq.push_back(c[i]);
		T1::build(now,qwq);
		getd(now,0,{now,now,0,0});
		vector<node> awa;
		for (int i=2;i<=tot;i++)
			if (d[c[i]].x!=-1&&d[c[i]].y!=-1&&T1::book[d[c[i]].x]==1&&T1::book[d[c[i]].y]==1)
				awa.push_back(d[c[i]]);
		ans+=2;
		for (int i=0;i<awa.size();i++)
			if (awa[i].l==awa[i].c)ans+=2;
		ans+=QwQ::calc(awa);
		for (int i=first[now];i;i=nxt[i]){
			if (book[v[i]]==1)continue;
			tot=0;
			getid(v[i],0);
			awa.clear();
			for (int j=1;j<=tot;j++)
				if (d[c[j]].x!=-1&&d[c[j]].y!=-1&&T1::book[d[c[j]].x]==1&&T1::book[d[c[j]].y]==1)
					awa.push_back(d[c[j]]);
			ans-=QwQ::calc(awa);
		}
		T1::clear();
		getrt(now,0);
		for (int i=first[now];i;i=nxt[i]){
			if (book[v[i]]==1)continue;
			sum=sz[v[i]],rt=0;
			getrt(v[i],now);
			work(rt);
		}
		return;
	}
}
int main(){
	n=read();
	Init::work();
	T1::init();
	T2::init();
	T2::work(1);
if (fg==1)cout<<QwQ::qwq_cnt<<endl;
	else cout<<ans/2<<endl;
	return 0;
}

Source code, Language: C++14

Details

answer.code: In member function ‘int QwQ::SGT::ask(int, int, int, int, int)’:
answer.code:209:76: error: return-statement with no value, in function returning ‘int’ [-fpermissive]
  209 |                 int ask(int now,int nowl,int nowr,int lt,int rt){if (fg==1)return;
      |                                                                            ^~~~~~