小日本的题目真无聊。。

膜1h领版的约大爷。

膜虐场AK__shi。

T1 无聊的题答。。直接弃疗

T2 傻逼DP题。直接DP，用括号序列维护一下，nlogn

#include<cstdio>
#include<algorithm>
#define N 100010
#define M 200010
using namespace std;
long long f[N],g[N],tot,sz[M],sz1[M];
int X[N],Y[N],Z[N],dad[17][N],l,cs[N],kt[N],jw[N],cf;
int n,i,x,y,head[N],ne[M],v[M],na[N],heed[N],m,z;
void add(int x,int y)
{
	v[++l]=y;
	ne[l]=head[x];
	head[x]=l;
}
void dfs(int x)
{
	cs[x]=cs[dad[0][x]]+1;
	kt[x]=++l;
	int t;
	for(t=0;dad[t][x];t++)
		dad[t+1][x]=dad[t][dad[t][x]];
	if(t>cf)cf=t-1;
	for(int i=head[x];i;i=ne[i])
	if(v[i]!=dad[0][x])
	{
		dad[0][v[i]]=x;
		dfs(v[i]);
	}
	jw[x]=++l;
}
int lca(int x,int y)
{
	if(cs[y]<cs[x])swap(x,y);
	for(int t=cf;t>=0;t--)
		if(cs[dad[t][y]]>=cs[x])y=dad[t][y];
	if(x==y)return x;
	for(int t=cf;t>=0;t--)
		if(dad[t][x]!=dad[t][y])
			x=dad[t][x],y=dad[t][y];
	return dad[0][x];
}
void aad(int x,long long y)
{
	for(;x<=l;x+=x&-x)
		sz[x]+=y;
}
long long calc(int x)
{
	long long y=0;
	for(;x;x-=x&-x)
		y+=sz[x];
	return y;
}
void aaa(int x,long long y)
{
	for(;x<=l;x+=x&-x)
		sz1[x]+=y;
}
long long caac(int x)
{
	long long y=0;
	for(;x;x-=x&-x)
		y+=sz1[x];
	return y;
}
void count(int x)
{
	for(int i=head[x];i;i=ne[i])
		if(v[i]!=dad[0][x])
		{
			count(v[i]);
			g[x]+=f[v[i]];
		}
	f[x]=g[x];
	aad(kt[x],g[x]);
	aad(jw[x],-g[x]);
	for(int i=heed[x];i;i=na[i])
	{
		tot=calc(kt[X[i]])-calc(jw[x])+Z[i];
		tot+=calc(kt[Y[i]])-calc(kt[x]);
		tot-=caac(kt[X[i]])+caac(kt[Y[i]])-2*caac(kt[x]);
		if(tot>f[x])f[x]=tot;
	}
	aaa(kt[x],f[x]);
	aaa(jw[x],-f[x]);
}
int main()
{
	scanf("%d",&n);
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	l=0;dfs(1);
	scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&X[i],&Y[i],&Z[i]);
		z=lca(X[i],Y[i]);
		na[i]=heed[z];heed[z]=i;
	}
	count(1);
	printf("%lld\n",f[1]);
}

T3 超级傻逼数据结构。直接线段树暴力搞。。刚刚开始忘记判k=1T了一发。。否则就能成为第三个200分的了QAQ

#include<cstdio>
#define N 100010 
#define M 400010
using namespace std;
int n,m,k,i,x,y,z;
long long sum[M];
void add(int l,int r,int x,int y,int cur)
{
	if(l==r){sum[cur]=y;return;}
	int mid=(l+r)>>1;
	if(x<=mid)add(l,mid,x,y,cur<<1);
	else add(mid+1,r,x,y,cur<<1|1);
	sum[cur]=sum[cur<<1]+sum[cur<<1|1];
}
void biu(int l,int r,int L,int R,int cur)
{
	if(l==r){sum[cur]/=k;return;}
	int mid=(l+r)>>1;
	if(L<=mid&&sum[cur<<1])biu(l,mid,L,R,cur<<1);
	if(R>mid&&sum[cur<<1|1])biu(mid+1,r,L,R,cur<<1|1);
	sum[cur]=sum[cur<<1]+sum[cur<<1|1];
}
long long count(int l,int r,int L,int R,int cur)
{
	if(L<=l&&R>=r)return sum[cur];
	int mid=(l+r)>>1;
	long long ans=0;
	if(L<=mid)ans+=count(l,mid,L,R,cur<<1);
	if(R>mid)ans+=count(mid+1,r,L,R,cur<<1|1);
	return ans;
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(i=1;i<=n;i++)
		scanf("%d",&x),add(1,n,i,x,1);
	while(m--)
	{
		scanf("%d%d%d",&x,&y,&z);
		if(x==1)add(1,n,y,z,1);
		if(x==2&&k>1)biu(1,n,y,z,1);
		if(x==3)printf("%lld\n",count(1,n,y,z,1));
	}
}

好无聊啊，期待day2。

（出数据结构的结果就是中国队AK啊。。）