Submission #107504

#	Time	Username	Problem	Language	Result	Execution time	Memory
107504		aer0park	트리 (KOI16_tree)	C++14	0 / 100	6 ms	5220 KiB

tree

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n,q,cnt=1;
ll ind[200004],pw[200004],chd[200004],par[200004];
vector<ll> g[200004];  //원래 번호 

ll val(ll a)
{
	ll ret=0;
	while(a)
	{
		ret+=pw[a];
		a-=(a&-a);	
	}	
	return ret;
}

void upd(ll a,ll x)
{
	while(a<=n)
	{
		pw[a]+=x;
		a+=(a&-a);
	}	
}

void updrange(ll a,ll sz,ll sum)
{
	ll now=val(a);
	upd(a,sum-now);
	upd(a+sz,-sum+now);
}

ll dfs(ll a,ll p)
{
	ll ret=1;
	ind[a]=cnt++,par[a]=ind[p];
	for(int i=0;i<g[a].size();i++)
		ret+=dfs(g[a][i],a);
	chd[ind[a]]=ret;
	return ret;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
	cin>>n>>q;
	for(int i=2;i<=n;i++)
	{
		ll a;cin>>a;
		g[a].push_back(i);
	}    
	dfs(1,0);
	for(int i=0;i<q;i++)
	{
		ll b,c,d;cin>>b>>c>>d;
		if(d==0)
		{
			if(val(ind[b])==val(ind[c]))
				cout<<"YES"<<"\n";
			else
				cout<<"NO"<<"\n";
		}
		else
		{
			if(val(ind[b])==val(ind[c]))
			{
				cout<<"YES"<<"\n";
				ll f=ind[b];
				if(val(f)==val(par[f])&&par[f]!=0)
					updrange(f,chd[f],f);
			}
			else
			{
				cout<<"NO"<<"\n";
				ll f=ind[c];
				if(val(f)==val(par[f])&&par[f]!=0)
					updrange(f,chd[f],f);	
			}
		}
	}
    return 0;
}

Compilation message (stderr)

tree.cpp: In function 'll dfs(ll, ll)':
tree.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[a].size();i++)
              ~^~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 13
• Subtask 3: 0 / 14
• Subtask 4: 0 / 19
• Subtask 5: 0 / 45