lyzlyz?lyzlyz!

惯例开坑。

任务栏：

订正了几题？2/3

bzoj刷题量？289/300

距离完成任务遥遥无期啊~~~

T1

令数列f_i=1(0≤i<k)，f_i=f_i-k+f_i-k+1(i≥k),求f_n%2^p。

首先k³logn的矩乘狠好写。

由于这是一个数列，假设已知：

[tex]f_n=\sum_{i=0}^{k-1}a_if_{n-k+i}[/tex]

那么可以k²求出b_i使得：

[tex]f_n=\sum_{i=0}^{k-1}b_if_{n-2k+i}[/tex]

那么只要倍增优化即可。

对于p=128的情形，出题人用__int128水过去了，然而我的c++并不兹磁。

然后就弃疗了。

T2

给一个长度为n的环，每次随机覆盖一个区间，问将所有段都覆盖至少一遍的期望步数。

非环情况详见Contest20160219滚粗记T3。

可以利用类似的（相同的）dp，每次枚举第一个白点的位置，然后计算。

由于要保留20位小数，需要使用高精度。

T3

令F(S)（S为一个可重集合）为最小的x，使得任意S的子集S‘的所有元素之和均不为x。

给定一棵树，每次询问从u到v的路径的点权集合S，加入k个元素后F(S)的最大值。

如果不加入元素，可以参考bzoj4408。

令ans=1，然后用主席树询问u~v的路径上在[1,ans]的点权之和，然后更新ans。

如果无法更新了，就添加一个元素ans+1，ans更新为ans*2+1。

显然发现：当ans大于某个值时，u~v的路径上的点权之和一直无法更新ans，那么ans只会变成ans*2+1。

那么就可以用高精度来处理。

【Codes】

#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
int n,K,i,j,k,p;
ll dp[55][3010],ans[3010],sum[3010];
void add(ll x,ll y){
	ans[0]+=x/y;
	x%=y;
	while (x<0)ans[0]--,x+=y;
	for (int i=1;i<=30;i++){
		x*=10;
		ans[i]+=x/y;
		x%=y;
	}
	for (int i=30;i;i--)ans[i-1]+=ans[i]/10,ans[i]%=10;
}
int main(){
	scanf("%d%d",&n,&K);
	int m=n*(n+1)/2;
	sum[n*n]=1;
	for (p=1;p<=n;p++){
		memset(dp,0,sizeof dp);
    	dp[p][0]=1;
    	for (i=p;i<=n;i++)
        	for (j=0;j<=m;j++)
				if (dp[i][j]){
        			sum[j+(n+p-i)*(n+p-i-1)/2]+=dp[i][j];
        			for (k=i+1;k<=n;k++)dp[k][j+(k-i)*(k-i-1)/2]-=dp[i][j];
        		}
    }
    ans[0]=1;
    for (i=1;i<n*n;i++)if (sum[i])add(sum[i]*i,n*n-i);
    printf("%lld.",ans[0]);
    for (i=1;i<=K;i++)printf("%d",ans[i]);
}

#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
typedef long double ld;
using namespace std;
const int M=200010;
int n,m,i,x,y,k,now,edgenum,cnt,N;
int a[M],head[M],vet[M],next[M],dep[M],fa[M][20],root[M];
struct node{int l,r;ll w;}tree[M*20];
struct bignum{int a[10];}Ans;
bignum operator * (bignum x,int y){
	for (int i=1;i<=x.a[0];i++)x.a[i]=x.a[i]*y;
	for (int i=1;i<=x.a[0];i++)if (x.a[i]>=1000000000)x.a[i+1]+=1,x.a[i]-=1000000000;
	if (x.a[x.a[0]+1])x.a[0]=x.a[0]+1;
	return x;
}
bignum operator + (bignum x,int y){
	x.a[1]+=1;
	int i=1;
	while (x.a[i]>=1000000000){x.a[i+1]+=1;x.a[i]-=1000000000;i++;}
	if (x.a[x.a[0]+1])x.a[0]=x.a[0]+1;
	return x;
}
void print(bignum x){
	printf("%d",x.a[x.a[0]]);
	for (int i=x.a[0]-1;i;i--){
		if (x.a[i]<100000000)printf("0");
		if (x.a[i]<10000000)printf("0");
		if (x.a[i]<1000000)printf("0");
		if (x.a[i]<100000)printf("0");
		if (x.a[i]<10000)printf("0");
		if (x.a[i]<1000)printf("0");
		if (x.a[i]<100)printf("0");
		if (x.a[i]<10)printf("0");
		printf("%d",x.a[i]);
	}
	puts("");
}
void addedge(int x,int y){
	vet[++edgenum]=y;
	next[edgenum]=head[x];
	head[x]=edgenum;
}
ll query(int x,int y,int l,int r,int a,int b,int c,int d){
	if (x==l&&y==r)return tree[a].w+tree[b].w-tree[c].w-tree[d].w;
	int mid=l+r>>1;
	if (y<=mid)return query(x,y,l,mid,tree[a].l,tree[b].l,tree[c].l,tree[d].l);
		else if (x>mid)return query(x,y,mid+1,r,tree[a].r,tree[b].r,tree[c].r,tree[d].r);
			else return query(x,mid,l,mid,tree[a].l,tree[b].l,tree[c].l,tree[d].l)+query(mid+1,y,mid+1,r,tree[a].r,tree[b].r,tree[c].r,tree[d].r);
}
void update(int x,int l,int r,int &p){
	tree[++cnt]=tree[p];p=cnt;tree[p].w+=x;
	if (l==r)return;
	int mid=l+r>>1;
	if (x<=mid)update(x,l,mid,tree[p].l);
		else update(x,mid+1,r,tree[p].r);
}
int lca(int x,int y){
	if (dep[x]<dep[y])swap(x,y);
	int t=dep[x]-dep[y];
	for (int i=0;i<=16;i++)
		if (t&(1<<i))x=fa[x][i];
	for (int i=16;i>=0;i--)
		if (fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	if (x==y)return x;
	return fa[x][0];
}
void dfs(int u,int pre){
	fa[u][0]=pre;
	for (int i=1;i<=16;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
	root[u]=root[pre];
	update(a[u],1,N,root[u]);
	for (int e=head[u];e;e=next[e]){
		int v=vet[e];
		if (v==pre)continue;
		dep[v]=dep[u]+1;
		dfs(v,u);
	}
}
int main(){
	scanf("%d",&n);
	for (i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		addedge(x,y);
		addedge(y,x);
	}
	for (i=1;i<=n;i++)scanf("%d",&a[i]),N=max(N,a[i]);
	dfs(1,0);
	scanf("%d",&m);
	while (m--){
		scanf("%d%d%d",&x,&y,&k);
		int z=lca(x,y);
		ll ans=1,add=0;
		while (1){
			if (ans>N)now=N;else now=ans;
			ll tmp=query(1,now,1,N,root[x],root[y],root[z],root[fa[z][0]])+add;
			if (tmp<ans){
				if (k){k--,add+=tmp+1;}
					else break;
			}
			ans=tmp+1;
			if (ans>1ll*100000000*100000000)break;
		}
		ans--;
		for (i=1;i<=Ans.a[0];i++)Ans.a[i]=0;
		Ans.a[1]=ans%1000000000;Ans.a[2]=ans/1000000000;if (Ans.a[2])Ans.a[0]=2;else Ans.a[0]=1;
		while (k)Ans=Ans*2+1,k--;
		print(Ans+1);
	}
}