QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#100775#5017. 相等树链1kri0 1603ms350276kbC++148.4kb2023-04-27 23:12:262023-04-27 23:12:30

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 23:12:30]
  • 评测
  • 测评结果：0
  • 用时：1603ms
  • 内存：350276kb
查看
  • [2023-04-27 23:12: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;
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]);
		}
		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 (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 (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;
	}
	ll calc(int rt,vector<node> _d){
		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(rt);
		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(now,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(v[i],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);
	cout<<ans/2<<endl;
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 50ms
memory: 281312kb

input:

5000
1296 1400 867 4533 1296 2007 2059 115 821 2960 3187 1597 2409 2708 4743 4778 1345 3967 911 3400 4249 3793 339 3145 3490 607 4148 3513 3264 3852 568 775 828 1348 423 3678 305 1938 1096 1373 2662 1048 4328 4208 203 779 3103 3372 4523 192 264 792 4943 2211 2494 3513 3555 4935 3277 3390 4624 128 18...

output:

77585

result:

wrong answer 1st numbers differ - expected: '76002', found: '77585'

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 1603ms
memory: 350276kb

input:

200000
13177 40498 104798 83659 186055 32788 86489 72123 13521 134868 158968 60124 166316 163390 120935 103000 83938 57807 97940 40447 137723 154683 191864 59080 102808 3969 21451 165592 128776 49468 4101 26441 139317 59503 18053 118809 187783 149816 21609 98521 165692 52964 60425 23437 29614 106886...

output:

5924126

result:

wrong answer 1st numbers differ - expected: '5859368', found: '5924126'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

Server Time: 2025-01-21 00:51:40 | OpenSource Project