codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

855.md (20237B)


      1 Source: https://codeforces.com/blog/entry/54750
      2 
      3 Tutorial is loading...
      4 
      5 **Solution**
      6 
      7 ```
      8 #include<bits/stdc++.h>
      9 using namespace std;
     10 #define sd(x) scanf("%d",&x)
     11 #define slld(x) scanf("%lld",&x)
     12 #define ss(x) scanf("%s",x)
     13 #define ll long long
     14 #define mod 1000000007
     15 #define bitcount    __builtin_popcountll
     16 #define pb push_back
     17 #define fi first
     18 #define se second
     19 #define mp make_pair
     20 #define pi pair<int,int>
     21 int main()
     22 {
     23     //freopen("in.txt","r",stdin);
     24     //freopen("out.txt","w",stdout);
     25     int n,i,j;
     26     string s[102];
     27     sd(n);
     28     for(i=0;i<n;i++)
     29     {
     30     	cin>>s[i];
     31     	for(j=0;j<i;j++)
     32     	{
     33     		if(s[i]==s[j])
     34     			break;
     35     	}
     36     	if(j==i)
     37     		printf("NO\n");
     38     	else
     39     		printf("YES\n");
     40     }
     41     return 0;
     42 }
     43 ```
     44 
     45 Tutorial is loading...
     46 
     47 **DP solution 1**
     48 
     49 ```
     50 #include<bits/stdc++.h>
     51 using namespace std;
     52 #define sd(x) scanf("%d",&x)
     53 #define slld(x) scanf("%lld",&x)
     54 #define ss(x) scanf("%s",x)
     55 #define ll long long
     56 #define mod 1000000007
     57 #define bitcount    __builtin_popcountll
     58 #define pb push_back
     59 #define fi first
     60 #define se second
     61 #define mp make_pair
     62 #define pi pair<int,int>
     63 int a[100005];
     64 ll dp[100005][3];
     65 int main()
     66 {
     67     //freopen("in.txt","r",stdin);
     68     //freopen("out.txt","w",stdout);
     69     int n,p,q,r,i;
     70     sd(n);
     71     sd(p);
     72     sd(q);
     73     sd(r);
     74     for(i=0;i<n;i++)
     75     	sd(a[i]);
     76     dp[0][0]=1ll*p*a[0];
     77     for(i=1;i<n;i++)
     78     	dp[i][0]=max(dp[i-1][0],1ll*p*a[i]);
     79     dp[0][1]=dp[0][0]+1ll*q*a[0];
     80     for(i=1;i<n;i++)
     81     	dp[i][1]=max(dp[i-1][1],dp[i][0]+1ll*q*a[i]);
     82     dp[0][2]=dp[0][1]+1ll*r*a[0];
     83     for(i=1;i<n;i++)
     84     	dp[i][2]=max(dp[i-1][2],dp[i][1]+1ll*r*a[i]);
     85     printf("%lld\n",dp[n-1][2]);
     86     return 0;
     87 }
     88 ```
     89 
     90 **DP solution 2 with minimum and maximum computation**
     91 
     92 ```
     93 #include<bits/stdc++.h>
     94 using namespace std;
     95 #define sd(x) scanf("%d",&x)
     96 #define slld(x) scanf("%lld",&x)
     97 #define ss(x) scanf("%s",x)
     98 #define mod 1000000007
     99 #define bitcount __builtin_popcountll
    100 #define ll long long
    101 #define pb push_back
    102 #define pi pair<int,int>
    103 #define pii pair<pi,int>
    104 #define mp make_pair
    105 int minleft[100005],minright[100005],maxleft[100005],maxright[100005],a[100005];
    106 int main()
    107 {
    108 	int i,j,k;
    109 	int n,p,q,r;
    110 	cin>>n>>p>>q>>r;
    111 	for(i=1;i<=n;i++)
    112 		sd(a[i]);
    113 	minleft[1]=maxleft[1]=a[1];
    114 	minright[n]=maxright[n]=a[n];
    115 	for(i=2;i<=n;i++)
    116 	{
    117 		minleft[i]=min(minleft[i-1],a[i]);
    118 		maxleft[i]=max(maxleft[i-1],a[i]);
    119 	}
    120 	for(i=n-1;i>=1;i--)
    121 	{
    122 		minright[i]=min(minright[i+1],a[i]);
    123 		maxright[i]=max(maxright[i+1],a[i]);
    124 	}
    125 	ll ans=-3e18;
    126 	for(i=1;i<=n;i++)
    127 	{
    128 		ll leftval = (p<0) ? 1ll*minleft[i]*p : 1ll*maxleft[i]*p;
    129 		ll rightval = (r<0) ? 1ll*minright[i]*r : 1ll*maxright[i]*r;
    130 		ans=max(ans,leftval+rightval+1ll*q*a[i]);
    131 	}
    132 	cout<<ans<<endl;
    133 	return 0;
    134 }
    135 ```
    136 
    137 Tutorial is loading...
    138 
    139 **Solution**
    140 
    141 ```
    142 #include<bits/stdc++.h>
    143 using namespace std;
    144 #define sd(x) scanf("%d",&x)
    145 #define slld(x) scanf("%lld",&x)
    146 #define ss(x) scanf("%s",x)
    147 #define ll long long
    148 #define mod 1000000007
    149 #define bitcount    __builtin_popcountll
    150 #define pb push_back
    151 #define fi first
    152 #define se second
    153 #define mp make_pair
    154 #define pi pair<int,int>
    155 int dp[100005][3][12],x,k,m;
    156 int a[3][12],b[3][12];
    157 vector <int> q[100005];
    158 void dfs(int cur,int par)
    159 {
    160 	int i,j=0,l,r,temp;
    161 	for(i=0;i<q[cur].size();i++)
    162 	{
    163 		if(q[cur][i]==par)
    164 			continue;
    165 		j=1;
    166 		dfs(q[cur][i],cur);
    167 	}
    168 	if(!j)
    169 	{
    170 		dp[cur][0][0]=k-1;
    171 		dp[cur][1][1]=1;
    172 		dp[cur][2][0]=m-k;
    173 		return;
    174 	}
    175 	for(i=0;i<3;i++)
    176 	{
    177 		for(j=0;j<=x;j++)
    178 		{
    179 			a[i][j]=0;
    180 			b[i][j]=0;
    181 		}
    182 	}
    183 	for(i=0;i<3;i++)
    184 		a[i][0]=1;
    185 	for(i=0;i<q[cur].size();i++)
    186 	{
    187 		if(q[cur][i]==par)
    188 			continue;
    189 		for(j=0;j<3;j++)
    190 		{
    191 			for(l=0;l<=x;l++)
    192 			{
    193 				for(r=0;r<=x;r++)
    194 				{
    195 					if(l+r>x)
    196 						continue;
    197 					if(j==0)
    198 					{
    199 						temp=dp[q[cur][i]][0][r]+dp[q[cur][i]][1][r];
    200 						if(temp>=mod)
    201 							temp-=mod;
    202 						temp+=dp[q[cur][i]][2][r];
    203 						if(temp>=mod)
    204 							temp-=mod;
    205 						b[j][l+r]+=(1ll*a[j][l]*temp)%mod;
    206 						if(b[j][l+r]>=mod)
    207 							b[j][l+r]-=mod;
    208 					}
    209 					else if(j==1)
    210 					{
    211 						b[j][l+r]+=(1ll*a[j][l]*(dp[q[cur][i]][0][r]))%mod;
    212 						if(b[j][l+r]>=mod)
    213 							b[j][l+r]-=mod;
    214 					}
    215 					else
    216 					{
    217 						temp=dp[q[cur][i]][0][r]+dp[q[cur][i]][2][r];
    218 						if(temp>=mod)
    219 							temp-=mod;
    220 						b[j][l+r]+=(1ll*a[j][l]*temp)%mod;
    221 						if(b[j][l+r]>=mod)
    222 							b[j][l+r]-=mod;
    223 					}
    224 				}
    225 				
    226 			}
    227 		}
    228 		for(j=0;j<3;j++)
    229 		{
    230 			for(l=0;l<=x;l++)
    231 			{
    232 				a[j][l]=b[j][l];
    233 				b[j][l]=0;
    234 			}
    235 		}
    236 	}
    237 	for(l=0;l<=x;l++)
    238 	{
    239 		dp[cur][0][l]=(1ll*a[0][l]*(k-1))%mod;
    240 		if(l>=1)
    241 			dp[cur][1][l]=a[1][l-1];
    242 		dp[cur][2][l]=(1ll*a[2][l]*(m-k))%mod;
    243 	}
    244 }
    245 int main()
    246 {
    247     //freopen("in.txt","r",stdin);
    248     //freopen("out.txt","w",stdout);
    249     int n,i,j,ans;
    250     sd(n);
    251     sd(m);
    252     for(i=1;i<n;i++)
    253     {
    254     	sd(j);
    255     	sd(k);
    256     	q[j].pb(k);
    257     	q[k].pb(j);
    258     }
    259     sd(k);
    260     sd(x);
    261     dfs(1,0);
    262     ans=0;
    263     for(i=0;i<3;i++)
    264     {
    265     	for(j=0;j<=x;j++)
    266     	{
    267     		//printf("%d %d %d\n",i,j,dp[1][i][j]);
    268     		ans+=dp[1][i][j];
    269     		if(ans>=mod)
    270     			ans-=mod;
    271     	}
    272     }
    273     printf("%d\n",ans);
    274     return 0;
    275 }
    276 ```
    277 
    278 Tutorial is loading...
    279 
    280 **Solution**
    281 
    282 ```
    283 #include<bits/stdc++.h>
    284 using namespace std;
    285 #define sd(x) scanf("%d",&x)
    286 #define slld(x) scanf("%lld",&x)
    287 #define ss(x) scanf("%s",x)
    288 #define mod 1000000007
    289 #define bitcount __builtin_popcountll
    290 #define ll long long
    291 #define pb push_back
    292 #define pi pair<int,int>
    293 #define pii pair<pi,int>
    294 #define mp make_pair
    295 vector<int>v[100005],v2[100005];
    296 int inherit[100005],comp[100005],parent[100005][25],height[100005];
    297 int parr[100005];
    298 int findpar(int node)
    299 {
    300 	return parr[node]==node ? node : parr[node]=findpar(parr[node]);
    301 }
    302 void dfs(int node, int par, int inh, int com)
    303 {
    304 	parent[node][0]=par;
    305 	inherit[node]=inh;
    306 	comp[node]=com;
    307 	height[node]=height[par]+1;
    308 	for(int i=1;i<=20;i++)
    309 	{
    310 		parent[node][i]=parent[parent[node][i-1]][i-1];
    311 	}
    312 	for(int i=0;i<v[node].size();i++)
    313 	{
    314 		if(v[node][i]==par)
    315 			continue;
    316 		if(v2[node][i]==0)
    317 			dfs(v[node][i],node,inh+1,com);
    318 		else
    319 			dfs(v[node][i],node,inh,com+1);
    320 	}
    321 }
    322 int findlca(int u, int v)
    323 {
    324 	if(height[u]>height[v])
    325 		swap(u,v);
    326 	for(int i=20;i>=0;i--)
    327 	{
    328 		if(height[parent[v][i]]>=height[u])
    329 		{
    330 			v=parent[v][i];
    331 		}
    332 	}
    333 	if(u!=v)
    334 	{
    335 		for(int i=20;i>=0;i--)
    336 		{
    337 			if(parent[u][i]!=parent[v][i])
    338 			{
    339 				u=parent[u][i];
    340 				v=parent[v][i];
    341 			}
    342 		}
    343 		u=parent[u][0];
    344 		v=parent[v][0];
    345 	}
    346 	return u;
    347 }
    348 int main()
    349 {
    350 	int i,j,k;
    351 	int n,q;
    352 	sd(n);
    353 	for(i=1;i<=n;i++)
    354 		parr[i]=i;
    355 	for(i=1;i<=n;i++)
    356 	{
    357 		sd(j);
    358 		sd(k);
    359 		if(j==-1 && k==-1)
    360 			continue;
    361 		v[i].pb(j);
    362 		v[j].pb(i);
    363 		v2[i].pb(k);
    364 		v2[j].pb(k);
    365 		int x=findpar(i);
    366 		int y=findpar(j);
    367 		if(x!=y)
    368 			parr[x]=y;
    369 	}
    370 	for(i=1;i<=n;i++)
    371 	{
    372 		if(parent[i][0]==0)
    373 		{
    374 			dfs(i,i,0,0);
    375 		}
    376 	}
    377 	sd(q);
    378 	while(q--)
    379 	{
    380 		sd(i);
    381 		sd(j);
    382 		sd(k);
    383 		int x=findpar(j);
    384 		int y=findpar(k);
    385 		if(x!=y)
    386 		{
    387 			printf("NO\n");
    388 			continue;
    389 		}
    390 		x=findlca(j,k);
    391 		if(i==1)
    392 		{
    393 			if(x!=j || comp[k]-comp[x]!=0 || j==k)
    394 			{
    395 				printf("NO\n");
    396 			}
    397 			else
    398 				printf("YES\n");
    399 		}
    400 		else
    401 		{
    402 			if(inherit[k]-inherit[x]!=0 || comp[j]-comp[x]!=0 || x==k)
    403 				printf("NO\n");
    404 			else
    405 				printf("YES\n");
    406 		}
    407 	}
    408 	return 0;
    409 }
    410 ```
    411 
    412 Tutorial is loading...
    413 
    414 **Solution**
    415 
    416 ```
    417 #include<bits/stdc++.h>
    418 using namespace std;
    419 #define sd(x) scanf("%lld",&x)
    420 #define slld(x) scanf("%lld",&x)
    421 #define ss(x) scanf("%s",x)
    422 #define ll long long
    423 #define mod 1000000007
    424 #define bitcount    __builtin_popcountll
    425 #define pb push_back
    426 #define fi first
    427 #define se second
    428 #define mp make_pair
    429 #define pi pair<int,int>
    430 ll dp[11][2][1030][70];
    431 ll len[12],a[100];
    432 ll f(ll b,ll in,ll m,ll pos)
    433 {
    434 	if(dp[b][in][m][pos]!=-1)
    435 		return dp[b][in][m][pos];
    436 	if(pos==0)
    437 	{
    438 		if(in!=0&&m==0)
    439 			return dp[b][in][m][pos]=1;
    440 		else
    441 			return dp[b][in][m][pos]=0;
    442 		return dp[b][in][m][pos];
    443 	}
    444 	ll j=0;
    445 	if(in==0)
    446 		j+=f(b,0,m,pos-1);
    447 	else
    448 		j+=f(b,1,(m^1),pos-1);
    449 	for(ll i=1;i<b;i++)
    450 		j+=f(b,1,(m^(1<<i)),pos-1);
    451 	dp[b][in][m][pos]=j;
    452 	return j;
    453 }
    454 int main()
    455 {
    456     //freopen("in.txt","r",stdin);
    457     //freopen("out.txt","w",stdout);
    458     ll n,i,j,k,in;
    459     ll ans,l,r,m,q,b;
    460     k=1e18;
    461     memset(dp,-1,sizeof dp);
    462     for(i=2;i<=10;i++)
    463     {
    464     	len[i]=1;
    465     	j=i;
    466     	while(j<k)
    467     	{
    468     		len[i]++;
    469     		j*=i;
    470     	}
    471     	f(i,0,0,len[i]+1);
    472     }
    473     sd(q);
    474     while(q--)
    475     {
    476     	sd(b);
    477     	sd(l);
    478     	sd(r);
    479     	ans=0;
    480     	l--;
    481     	if(l)
    482     	{
    483     		j=l;
    484     		i=0;
    485     		while(j)
    486     		{
    487     			a[i]=j%b;
    488     			j/=b;
    489     			i++;
    490     		}
    491     		m=0;
    492     		in=0;
    493     		for(j=i-1;j>=0;j--)
    494     		{
    495     			for(k=0;k<a[j];k++)
    496     			{
    497     				if(k!=0)
    498     					in=1;
    499     				if(in==0)
    500     					ans-=dp[b][0][m][j];
    501     				else
    502     					ans-=dp[b][1][(m^(1<<k))][j];
    503     			}
    504     			if(in|a[j])
    505     			{
    506     				in=1;
    507     				m=(m^(1<<a[j]));
    508     			}
    509     		}
    510     		ans-=dp[b][in][m][0];
    511     	}
    512     	j=r;
    513     	i=0;
    514     	while(j)
    515     	{
    516     		a[i]=j%b;
    517     		j/=b;
    518     		i++;
    519     	}
    520     	in=0;
    521     	m=0;
    522 		for(j=i-1;j>=0;j--)
    523 		{
    524 			for(k=0;k<a[j];k++)
    525 			{
    526 				if(k!=0)
    527 					in=1;
    528 				if(in==0)
    529 					ans+=dp[b][0][m][j];
    530 				else
    531 					ans+=dp[b][1][(m^(1<<k))][j];
    532 			}
    533 			if(in|a[j])
    534 			{
    535 				in=1;
    536 				m=(m^(1<<a[j]));
    537 			}
    538 		}
    539 		ans+=dp[b][in][m][0];
    540 		printf("%lld\n",ans);
    541     }
    542     return 0;
    543 }
    544 ```
    545 
    546 Tutorial is loading...
    547 
    548 **Solution**
    549 
    550 ```
    551 #include<bits/stdc++.h>
    552 using namespace std;
    553 #define sd(x) scanf("%d",&x)
    554 #define slld(x) scanf("%lld",&x)
    555 #define ss(x) scanf("%s",x)
    556 #define mod 1000000007
    557 #define bitcount __builtin_popcountll
    558 #define ll long long
    559 #define pb push_back
    560 #define fi first
    561 #define se second
    562 #define pi pair<int,int>
    563 #define pii pair<pi,int>
    564 #define mp make_pair
    565 ll ans[1000];
    566 int upper[1000],lower[1000];
    567 int block;
    568 map <int,int> low[1000],up[1000];
    569 map <int,int> vnotup[1000],vnotdown[1000];
    570 int notboth[1000];
    571 int minup[100005],mindown[100005];
    572 void updateup(int i,int l,int r,int val)
    573 {
    574 	if(upper[i]<=val)
    575 		return;
    576 	//map<int,int> m;
    577 	map<int,int> :: iterator it;
    578 	//m.clear();
    579 	for(int j=l;j<=r;j++)
    580 	{
    581 		if(minup[j]>val)
    582 		{
    583 			if(minup[j]==mod&&mindown[j]==mod&&upper[i]==mod&&lower[i]==mod)
    584 			{
    585 				notboth[i]--;
    586 				//notdown[i]++;
    587 				vnotdown[i][val]++;
    588 				//notdownsum[i]+=val;
    589 			}
    590 			else if(minup[j]==mod&&upper[i]==mod)
    591 			{
    592 				//notup[i]--;
    593 				int temp=min(lower[i],mindown[j]);
    594 				vnotup[i][temp]--;
    595 				if(vnotup[i][temp]==0)
    596 					vnotup[i].erase(temp);
    597 				//notupsum[i]-=min(lower[i],mindown[j]);
    598 				up[i][val]++;
    599 				low[i][temp]++;
    600 				ans[i]+=val;
    601 				ans[i]+=min(lower[i],mindown[j]);
    602 			}
    603 			else if(mindown[j]==mod&&lower[i]==mod)
    604 			{
    605 				int temp=min(upper[i],minup[j]);
    606 				vnotdown[i][temp]--;
    607 				if(vnotdown[i][temp]==0)
    608 					vnotdown[i].erase(temp);
    609 				vnotdown[i][val]++;
    610 			}
    611 			else
    612 			{
    613 				ans[i]+=val-min(upper[i],minup[j]);
    614 				up[i][min(minup[j],upper[i])]--;
    615 				up[i][val]++;
    616 			}
    617 			minup[j]=val;
    618 		}
    619 	}
    620 }
    621 void updatefullup(int i,int val)
    622 {
    623 	if(val>=upper[i])
    624 		return;
    625 	map <int,int> :: iterator it; 
    626 	int n=up[i].size();
    627 	n--;
    628 	ll sum=0;
    629 	int len2=0;
    630 	for(it=vnotup[i].begin();it!=vnotup[i].end();it++)
    631 	{
    632 		ans[i]+=1ll*(it->fi)*(it->se)+1ll*(it->se)*val;
    633 		len2+=it->se;
    634 		low[i][it->fi]+=it->se;
    635 	}
    636 	vnotup[i].clear();
    637 	it=vnotdown[i].upper_bound(val);
    638 	int temp=0;
    639 	for(it;it!=vnotdown[i].end();it++)
    640 	{
    641 		temp+=it->se;
    642 	}
    643 	it=vnotdown[i].upper_bound(val);
    644 	vnotdown[i].erase(it,vnotdown[i].end());
    645 	vnotdown[i][val]+=temp+notboth[i];
    646 	notboth[i]=0;
    647 	int len=0;
    648 	it=up[i].upper_bound(val);
    649 	for(it;it!=up[i].end();it++)
    650 	{
    651 		sum+=1ll*(it->fi)*(it->se);
    652 		len+=it->se;
    653 	}
    654 	it=up[i].upper_bound(val);
    655 	up[i].erase(it,up[i].end());
    656 	ans[i]+=1ll*len*val-sum;
    657 	up[i][val]+=len+len2;
    658 	upper[i]=val;
    659 }
    660 void updatedown(int i,int l,int r,int val)
    661 {
    662 	if(lower[i]<=val)
    663 		return;
    664 	//map<int,int> m;
    665 	map<int,int> :: iterator it;
    666 	//m.clear();
    667 	for(int j=l;j<=r;j++)
    668 	{
    669 		if(mindown[j]>val)
    670 		{
    671 			if(mindown[j]==mod&&minup[j]==mod&&upper[i]==mod&&lower[i]==mod)
    672 			{
    673 				notboth[i]--;
    674 				//notup[i]++;
    675 				//notupsum[i]+=val;
    676 				vnotup[i][val]++;
    677 			}
    678 			else if(mindown[j]==mod&&lower[i]==mod)
    679 			{
    680 				//notdown[i]--;
    681 				int temp=min(upper[i],minup[j]);
    682 				vnotdown[i][temp]--;
    683 				if(vnotdown[i][temp]==0)
    684 					vnotdown[i].erase(temp);
    685 				low[i][val]++;
    686 				up[i][temp]++;
    687 				//notdownsum[i]-=min(upper[i],minup[j]);
    688 				ans[i]+=val;
    689 				ans[i]+=min(upper[i],minup[j]);
    690 			}
    691 			else if(minup[j]==mod&&upper[i]==mod)
    692 			{
    693 				int temp=min(lower[i],mindown[j]);
    694 				vnotup[i][temp]--;
    695 				if(vnotup[i][temp]==0)
    696 					vnotup[i].erase(temp);
    697 				vnotup[i][val]++;
    698 			}
    699 			else
    700 			{
    701 				ans[i]+=val-min(lower[i],mindown[j]);
    702 				low[i][min(mindown[j],lower[i])]--;
    703 				low[i][val]++;
    704 			}
    705 			mindown[j]=val;
    706 		}
    707 	}
    708 }
    709 void updatefulldown(int i,int val)
    710 {
    711 	if(val>=lower[i])
    712 		return;
    713 	map <int,int> :: iterator it; 
    714 	int n=low[i].size();
    715 	n--;
    716 	ll sum=0;
    717 	int len2=0;
    718 	for(it=vnotdown[i].begin();it!=vnotdown[i].end();it++)
    719 	{
    720 		ans[i]+=1ll*(it->fi)*(it->se)+1ll*(it->se)*val;
    721 		len2+=it->se;
    722 		up[i][it->fi]+=it->se;
    723 	}
    724 	vnotdown[i].clear();
    725 	it=vnotup[i].upper_bound(val);
    726 	int temp=0;
    727 	for(it;it!=vnotup[i].end();it++)
    728 	{
    729 		temp+=it->se;
    730 	}
    731 	it=vnotup[i].upper_bound(val);
    732 	vnotup[i].erase(it,vnotup[i].end());
    733 	vnotup[i][val]+=temp+notboth[i];
    734 	notboth[i]=0;
    735 	int len=0;
    736 	it=low[i].upper_bound(val);
    737 	for(it;it!=low[i].end();it++)
    738 	{
    739 		sum+=1ll*(it->fi)*(it->se);
    740 		len+=it->se;
    741 	}
    742 	it=low[i].upper_bound(val);
    743 	low[i].erase(it,low[i].end());
    744 	ans[i]+=1ll*len*val-sum;
    745 	low[i][val]+=len+len2;
    746 	lower[i]=val;
    747 }
    748 ll query(int i,int l,int r)
    749 {
    750 	ll sum=0;
    751 	for(int j=l;j<=r;j++)
    752 	{
    753 		if(min(upper[i],minup[j])<mod&&min(lower[i],mindown[j])<mod)
    754 			sum+=min(upper[i],minup[j])+min(lower[i],mindown[j]);
    755 	}
    756 	return sum;
    757 }
    758 ll queryfull(int i)
    759 {
    760 	return ans[i];
    761 }
    762 int main()
    763 {
    764 	int i,j,k,q,n,t,l,r,val,block;
    765 	ll s;
    766 	n=100000;
    767 	for(i=0;i<1000;i++)
    768 		lower[i]=upper[i]=mod;
    769 	for(i=0;i<=100000;i++)
    770 		minup[i]=mindown[i]=mod;
    771 	block=300;
    772 	for(i=1;i<=n;i++)
    773 	{
    774 		j=i/block;
    775 		notboth[j]++;
    776 	}
    777 	sd(q);
    778 	while(q--)
    779 	{
    780 		sd(t);
    781 		sd(l);
    782 		sd(r);
    783 		r--;
    784 		if(t==1)
    785 		{
    786 			sd(val);
    787 			i=l/block;
    788 			j=r/block;
    789 			if(val>0)
    790 			{
    791 				if(i==j)
    792 					updateup(j,l,r,val);
    793 				else
    794 				{
    795 					updateup(i,l,(i+1)*block-1,val);
    796 					i++;
    797 					while(i<j)
    798 					{
    799 						// updateup(i,i*block,(i+1)*block-1,val);
    800 						updatefullup(i,val);
    801 						i++;
    802 					}
    803 					updateup(j,j*block,r,val);
    804 				}
    805 			}
    806 			else
    807 			{
    808 				if(i==j)
    809 					updatedown(j,l,r,-val);
    810 				else
    811 				{
    812 					updatedown(i,l,(i+1)*block-1,-val);
    813 					i++;
    814 					while(i<j)
    815 					{
    816 						// updatedown(i,i*block,(i+1)*block-1,-val);
    817 						updatefulldown(i,-val);
    818 						i++;
    819 					}
    820 					updatedown(j,j*block,r,-val);
    821 				}
    822 			}
    823 		}
    824 		else
    825 		{
    826 			s=0;
    827 			i=l/block;
    828 			j=r/block;
    829 			if(i==j)
    830 				s=query(j,l,r);
    831 			else
    832 			{
    833 				s=query(i,l,(i+1)*block-1);
    834 				i++;
    835 				while(i<j)
    836 				{
    837 					//s+=query(i,i*block,(i+1)*block-1);
    838 					s+=queryfull(i);
    839 					i++;
    840 				}
    841 				s+=query(j,j*block,r);
    842 			}
    843 			printf("%lld\n",s);
    844 		}
    845 	}
    846 	return 0;
    847 }
    848 ```
    849 
    850 Tutorial is loading...
    851 
    852 **Solution**
    853 
    854 ```
    855 #include <bits/stdc++.h>
    856 
    857 using namespace std;
    858 
    859 using ll = long long;
    860 using ld = long double;
    861 using D = double;
    862 using uint = unsigned int;
    863 template<typename T>
    864 using pair2 = pair<T, T>;
    865 
    866 #ifdef WIN32
    867     #define LLD "%I64d"
    868 #else
    869     #define LLD "%lld"
    870 #endif
    871 
    872 #define pb push_back
    873 #define mp make_pair
    874 #define all(x) (x).begin(),(x).end()
    875 #define fi first
    876 #define se second
    877 
    878 const int maxn = 200005;
    879 
    880 struct tpath
    881 {
    882     int rep, sz;
    883     ll ansmiddle;
    884     int edgeleft, edgeright;
    885 };
    886 
    887 int p[maxn], s[maxn];
    888 int sz[maxn], down[maxn], up[maxn], top[maxn];
    889 vector<tpath> path, path2;
    890 vector<int> gr[maxn];
    891 ll dp1[maxn], dp2[maxn], ansmiddle[maxn];
    892 int n, m;
    893 ll answer;
    894 int tin[maxn], tout[maxn];
    895 int timer;
    896 
    897 inline int find(int a)
    898 {
    899     return (a == p[a] ? a : p[a] = find(p[a]));
    900 }
    901 
    902 inline bool isparent(int a, int b)
    903 {
    904     return tin[a] <= tin[b] && tout[a] >= tin[b];
    905 }
    906 
    907 void unite(int a, int b)
    908 {
    909     a = find(a);
    910     b = find(b);
    911     if (a == b) return;
    912     if (s[a] > s[b]) swap(a, b);
    913     p[a] = b;
    914     if (s[a] == s[b]) s[b]++;
    915     if (tin[top[a]] < tin[top[b]])
    916     {
    917         sz[top[a]] += sz[top[b]];
    918         top[b] = top[a];
    919     } else
    920     {
    921         sz[top[b]] += sz[top[a]];
    922     }
    923 }
    924 
    925 void findpath(int a, int b)
    926 {
    927     a = top[find(a)];
    928     b = top[find(b)];
    929 //     cout << "findpath " << a << ' ' << b << endl;
    930     int lastdowna = 0;
    931     while (!isparent(a, b))
    932     {
    933         path.pb({a, sz[a], ansmiddle[a], lastdowna, n - down[a]});
    934         lastdowna = down[a];
    935         a = top[find(up[a])];
    936     }
    937     path2.clear();
    938     int lastdownb = 0;
    939     while (a != b)
    940     {
    941         path2.pb({b, sz[b], ansmiddle[b], n - down[b], lastdownb});
    942         lastdownb = down[b];
    943         b = top[find(up[b])];
    944     }
    945     path.pb({a, sz[a], ansmiddle[a], lastdowna, lastdownb});
    946     reverse(all(path2));
    947     for (auto t : path2) path.pb(t);
    948 }
    949 
    950 void addedge(int a, int b)
    951 {
    952     if (find(a) == find(b)) return;
    953     path.clear();
    954     findpath(a, b);
    955     
    956 //     cout << "addedge " << a << ' ' << b << endl;
    957 //     for (auto t : path) cout << "(" << t.rep << ' ' << t.sz << ' ' << t.ansmiddle << ' ' << t.edgeleft << ' ' << t.edgeright << ")" << endl;
    958     
    959     // 3
    960     ll cnt0 = 1;
    961     ll cnt1 = 0;
    962     ll cnt2 = 0;
    963     for (auto t : path)
    964     {
    965         answer -= t.sz * cnt2 * 2 + (ll)t.sz * (t.sz - 1) * cnt1 * 2 + (ll)t.sz * (t.sz - 1) * (t.sz - 2);
    966         cnt2 += t.sz * cnt1 + (ll)t.sz * (t.sz - 1) * cnt0;
    967         cnt1 += t.sz * cnt0;
    968     }
    969     ll sum = cnt1;
    970     answer += ((ll)sum * (sum - 1) * (sum - 2));
    971     
    972 //     cout << "after 3: " << answer << endl;
    973     
    974     // 2
    975     cnt1 = 0;
    976     for (auto t : path)
    977     {
    978         answer += cnt1 * (t.edgeleft - cnt1) * t.sz * 2;
    979         cnt1 += t.sz;
    980     }
    981     cnt1 = 0;
    982     for (int i = (int)path.size() - 1; i >= 0; i--)
    983     {
    984         auto &t = path[i];
    985         answer += cnt1 * (t.edgeright - cnt1) * t.sz * 2;
    986         cnt1 += t.sz;
    987     }
    988 
    989 //     cout << "after 2: " << answer << endl;    
    990     
    991     // 1
    992     cnt1 = 0;
    993     cnt2 = 0;
    994     for (auto t : path)
    995     {
    996         answer += cnt2 * t.sz * 2;
    997         cnt2 += (n - t.edgeright - t.edgeleft - t.sz) * cnt1;
    998         cnt1 += n - t.edgeright - t.edgeleft - t.sz;
    999     }
   1000     cnt1 = 0;
   1001     cnt2 = 0;
   1002     for (int i = (int)path.size() - 1; i >= 0; i--)
   1003     {
   1004         auto &t = path[i];
   1005         answer += cnt2 * t.sz * 2;
   1006         cnt2 += (n - t.edgeleft - t.edgeright - t.sz) * cnt1;
   1007         cnt1 += n - t.edgeleft - t.edgeright - t.sz;
   1008     }
   1009 //     cout << "after 1 old: " << answer << endl;
   1010     ll ttldown1 = 0;
   1011     ll ttldown2 = 0;
   1012     for (auto t : path)
   1013     {
   1014         ll curdown = n - t.edgeleft - t.edgeright - t.sz;
   1015         ll curdown2 = t.ansmiddle - curdown * (t.edgeleft + t.edgeright) * 2 - (ll)t.edgeleft * t.edgeright * 2;
   1016         answer += curdown2 * (sum - t.sz);
   1017         ttldown2 = ttldown2 + curdown2 + ttldown1 * curdown * 2;
   1018         ttldown1 += curdown;
   1019     }
   1020 
   1021 //     cout << "after 1: " << answer << endl;
   1022     
   1023     for (int i = 1; i < (int)path.size(); i++) unite(path[i - 1].rep, path[i].rep);
   1024     ansmiddle[top[find(path[0].rep)]] = ttldown2;
   1025 }
   1026 
   1027 int go(int cur, int pr)
   1028 {
   1029     down[cur] = 1;
   1030     up[cur] = pr;
   1031     dp1[cur] = 0;
   1032     ansmiddle[cur] = 0;
   1033     tin[cur] = timer++;
   1034     for (auto t : gr[cur]) if (t != pr)
   1035     {
   1036         down[cur] += go(t, cur);
   1037         answer += (ll)dp1[t] * dp1[cur] * 2;
   1038         answer += (ll)dp1[t] * dp2[cur] * 2 + dp2[t] * dp1[cur] * 2;
   1039         ansmiddle[cur] += (ll)dp1[t] * dp1[cur] * 2;
   1040         answer += dp2[t] * 2;
   1041         dp2[cur] += dp2[t];
   1042         dp1[cur] += dp1[t];
   1043     }
   1044     ansmiddle[cur] += (ll)(n - down[cur]) * dp1[cur] * 2;
   1045     dp2[cur] += dp1[cur];
   1046     dp1[cur] += 1;
   1047     tout[cur] = timer - 1;
   1048 //     cout << "exit " << cur << ' ' << answer << ' ' << dp1[cur] << ' ' << dp2[cur] << endl;
   1049     return down[cur];
   1050 }
   1051 
   1052 int main()
   1053 {
   1054     scanf("%d", &n);
   1055     for (int i = 0; i < n - 1; i++)
   1056     {
   1057         int a, b;
   1058         scanf("%d%d", &a, &b);
   1059         a--, b--;
   1060         gr[a].pb(b);
   1061         gr[b].pb(a);
   1062     }
   1063     go(0, -1);
   1064     for (int i = 0; i < n; i++)
   1065     {
   1066         p[i] = i;
   1067         s[i] = 0;
   1068         top[i] = i;
   1069         sz[i] = 1;
   1070     }
   1071     printf("%lld\n", answer);
   1072     scanf("%d", &m);
   1073     for (int i = 0; i < m; i++)
   1074     {
   1075         int a, b;
   1076         scanf("%d%d", &a, &b);
   1077         a--, b--;
   1078         addedge(a, b);
   1079         printf("%lld\n", answer);
   1080     }
   1081     
   1082     return 0;
   1083 }
   1084 ```