#2
Two Sets
题面
对于第一个要求，可以得到一个贪心的思路，拆位分析。如果该位异或和为 \(0\)，可以拆成 \(0,0\) 和 \(1,1\)，而且如果能拆成 \(1,1\)，则拆成 \(1,1\)。如果该位异或和为 \(1\)，可以拆成 \(0,1\) 和 \(1,0\)，根据第二个要求，能拆成 \(0,1\) 则拆成 \(0,1\)。
根据这个要求，我们可以得到若干个形如 \(\oplus_{i=1}^n a_{i,j}\times c_{i}=s_j\) 的异或方程，其中 $a_{i,j} 表示 \(a_i\) 的第 \(j\) 位的值，\(c_i\) 表示第 \(i\) 个数是否被选入第一个集合，\(s_j\) 表示该位异或的权值。解异或方程考虑使用高斯消元或者线性基。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e5+10,Lg=64;
int n,a[N],pos[70],all,cnt,res[N];
bitset<N>f[70];
void solve(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
all^=a[i];
}
for(int s=0;s<=1;s++){
for(int i=Lg-1;i>=0;i--){
if((all>>i&1)==s){
cnt++;
for(int j=1;j<=n;j++){
if(a[j]>>i&1){
f[cnt][j]=1;
}
}
f[cnt][n+1]=s^1;
for(int j=1;j<cnt;j++){
if(f[cnt][pos[j]]){
f[cnt]^=f[j];
}
}
pos[cnt]=0;
for(int j=1;j<=n;j++){
if(f[cnt][j]){
pos[cnt]=j;
break;
}
}
if(!pos[cnt]){
cnt--;
continue;
}
for(int j=1;j<cnt;j++){
if(f[j][pos[cnt]]){
f[j]^=f[cnt];
}
}
}
}
}
for(int i=0;i<Lg;i++){
res[pos[i]]=f[i][n+1];
}
for(int i=1;i<=n;i++){
write_space(2-res[i]);
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
[ARC130D] Zigzag Tree
题面
将大于周围的点的权值的点视作黑点，小于周围的点的权值的点视作白点，那么最后的树在染色后必然为一棵黑白相间的树，即可能的颜色方案只有两种，确定任意一个点的颜色都将确定整棵树所有点的颜色。
令 \(f_{u,i,0/1}\) 表示点 \(u\) 为白色或黑色且权值在子树中排名第 \(i\) 位的方案数，\(siz_u\) 表示合并前 \(u\) 所在连通块的大小。
转移考虑将点儿子 \(v\) 所在的子树合并到 \(u\) 所在的连通块中。以白色为例，枚举 \(u\) 原来在连通块中排第 \(i\)，子树 \(v\) 中有 \(j\) 个点权值小于 \(u\) 的权值，点 \(v\) 权值为子树中第 \(k\) 位，得到一个 \(O(n^3)\) 的 dp 式。
\[f_{u,i+j,0}=\sum\limits_{k=j+1}^{siz_v}f_{u,i,0}\times\binom{i+j-1}{j}\times\binom{siz_u+siz_v-i-j}{siz_v-j}\times f_{v,k,1}
\]
\[f_{u,i+j,1}=\sum\limits_{k=1}^j f_{u,i,1}\times\binom{i+j-1}{j}\times\binom{siz_u+siz_v-i-j}{siz_v-j}\times f_{v,k,0}
\]
容易发现将 \(\sum\limits_{k=j+1}^{siz_v} f_{v,k,1}\) 和 \(\sum\limits_{k=1}^j f_{v,k,0}\) 以外的部分提出，这两个部分做下前缀/后缀和即可。
总复杂度 \(O(n^2)\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=3e3+10,mod=998244353;
vector<int>e[N];
int n,fac[N],inv[N],f[N][N][2],g[N][2];
int qpow(int a,int b){
int res=1;
while(b){
if(b&1){
res=res*a%mod;
}
b>>=1;
a=a*a%mod;
}
return res;
}
void init(int mx){
fac[0]=1;
for(int i=1;i<=mx;i++){
fac[i]=fac[i-1]*i%mod;
}
inv[mx]=qpow(fac[mx],mod-2);
for(int i=mx-1;i>=0;i--){
inv[i]=inv[i+1]*(i+1)%mod;
}
}
int siz[N],pre[N],bac[N];
int C(int n,int m){
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
void dfs(int u,int father){
siz[u]=1;
f[u][1][0]=f[u][1][1]=1;
for(auto v:e[u]){
if(v==father){
continue;
}
dfs(v,u);
for(int i=0;i<=siz[v]+1;i++){
pre[i]=bac[i]=0;
}
for(int i=1;i<=siz[v];i++){
pre[i]=(pre[i-1]+f[v][i][0])%mod;
}
for(int i=siz[v];i;i--){
bac[i]=(bac[i+1]+f[v][i][1])%mod;
}
for(int i=0;i<=siz[u];i++){
for(int j=0;j<=siz[v];j++){
g[i+j][0]=(g[i+j][0]+C(i-1+j,j)*C(siz[u]-i+siz[v]-j,siz[v]-j)%mod*f[u][i][0]%mod*bac[j+1]%mod)%mod;
g[i+j][1]=(g[i+j][1]+C(i-1+j,j)*C(siz[u]-i+siz[v]-j,siz[v]-j)%mod*f[u][i][1]%mod*pre[j]%mod)%mod;
}
}
siz[u]+=siz[v];
for(int i=0;i<=siz[u];i++){
f[u][i][0]=g[i][0];
f[u][i][1]=g[i][1];
g[i][0]=g[i][1]=0;
}
}
}
void solve(){
read(n);
for(int i=1;i<n;i++){
int u,v;
read(u),read(v);
e[u].pb(v);
e[v].pb(u);
}
dfs(1,0);
int ans=0;
for(int i=1;i<=n;i++){
ans=(ans+f[1][i][0]+f[1][i][1])%mod;
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
init(3000);
int t=1;
while(t--){
solve();
}
return 0;
}
『MGOI』Simple Round I | D. 魔法环
题面
因为题目中有至少，可以发现 \(0\) 必选。
证明：假定选择了 \(0\) 左侧距离 \(0\) 的位置为 \(x\) 和右侧距离 \(0\) 的位置为 \(y\) 的两个点，权值分别为 \(a,b\)。不选 \(0\) 时，贡献为 \(\max(a,b)\times\frac{(x+y-1)(x+y)}{2}\)，选 \(0\) 时，贡献为 \(a\times \frac{x(x-1)}{2}+b\times \frac{y(y-1)}{2}\)，后者显然优于前者，故 \(0\) 必选。
考虑从 \(0\) 断环，令 \(f_{i,j}\) 表示前 \(i\) 个数中选了 \(j\) 个数，转移式为 \(f_{i,j}=f_{k,j-1}+a_i^2+\max(a_i,a_k)\times\frac{(k-i-1)(k-i)}{2}\)，复杂度为 \(O(n^3)\)。因为大于等于 \(K\) 的 \(j\) 本质相同，所以可以直接从 \(f_{k,K}\) 转移，复杂度变成了 \(O(n^2K)\)。
我也不知道为什么能过 \(n=3000,K=100\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=3010,K=110,inf=1e18;
int n,k,f[N][K],a[N<<1];
void solve(){
read(n),read(k);
for(int i=1;i<=n;i++){
read(a[i]);
a[n+i]=a[i];
}
for(int i=1;i<=n;i++){
if(a[i]==0){
for(int j=1;j<=n;j++){
a[j]=a[i+j-1];
}
break;
}
}
memset(f,0x3f,sizeof(f));
f[1][1]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=min(i,k);j++){
for(int p=1;p<i;p++){
f[i][j]=min(f[i][j],f[p][j-1]+(i-p-1)*(i-p)/2*max(a[i],a[p]));
if(j==k){
f[i][j]=min(f[i][j],f[p][j]+(i-p-1)*(i-p)/2*max(a[i],a[p]));
}
}
f[i][j]+=a[i]*a[i];
}
}
int ans=inf;
for(int i=1;i<=n;i++){
ans=min(ans,f[i][k]+(n-i)*(n-i+1)/2*a[i]);
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
[CEOI2017] One-Way Streets
题面
相当有趣的图论题。对于一个边双，因为里面任意两个点之间的路径至少有两条，所以里面的边均为无法确定。缩点后为一个森林，对于一条树边，将其表示为儿子到父亲的边。因为保证有解，所以不会同时存在从 \(u\) 到 \(v\) 和从 \(v\) 到 \(u\) 的路径，所以可以使用树上差分，在起点 \(+1\)，终点 \(-1\)。最后如果一个点的权值为正，表示该点到父亲的边方向指向父亲，为负则指向儿子，为 \(0\) 则无法确定。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e5+10;
int n,m,head[N],tot=1;
struct edge{
int v,nxt,id;
}e[N<<1],G[N<<1];
void add(int u,int v,int id){
e[++tot].v=v;
e[tot].id=id;
e[tot].nxt=head[u];
head[u]=tot;
}
void add_e(int u,int v,int id){
add(u,v,id);
add(v,u,id);
}
int dfn[N],low[N],stk[N],in_stack[N],top,idx,col[N],col_cnt;
void tarjan(int u,int from){
dfn[u]=low[u]=++idx;
stk[++top]=u;
in_stack[u]=1;
for(int i=head[u];i;i=e[i].nxt){
if((from^i^1)==0){
continue;
}
int v=e[i].v;
if(!dfn[v]){
tarjan(v,i);
low[u]=min(low[u],low[v]);
}
else if(in_stack[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
col[u]=++col_cnt;
in_stack[u]=0;
while(stk[top]!=u){
int v=stk[top];
col[v]=col_cnt;
in_stack[v]=0;
top--;
}
top--;
}
}
pii a[N];
int cnt=1,hd[N],vis[N],d[N],ans[N];
void dfs(int u,int from){
vis[u]=1;
for(int i=hd[u];i;i=G[i].nxt){
int v=G[i].v;
if(vis[v]){
continue;
}
dfs(v,i);
d[u]+=d[v];
}
if(d[u]>0){
if(from&1){
ans[G[from].id]=1;
}
else{
ans[G[from].id]=2;
}
}
else if(d[u]<0){
if(from&1){
ans[G[from].id]=2;
}
else{
ans[G[from].id]=1;
}
}
}
void solve(){
read(n),read(m);
for(int i=1,u,v;i<=m;i++){
read(u),read(v);
add_e(u,v,i);
a[i]=mp(u,v);
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(i,0);
}
}
for(int i=1;i<=m;i++){
int u=a[i].first,v=a[i].second;
if(col[u]!=col[v]){
G[++cnt].v=col[v];
G[cnt].id=i;
G[cnt].nxt=hd[col[u]];
hd[col[u]]=cnt;
G[++cnt].v=col[u];
G[cnt].id=i;
G[cnt].nxt=hd[col[v]];
hd[col[v]]=cnt;
}
}
int q;
read(q);
while(q--){
int u,v;
read(u),read(v);
d[col[u]]++;
d[col[v]]--;
}
for(int i=1;i<=col_cnt;i++){
if(!vis[i]){
dfs(i,0);
}
}
for(int i=1;i<=m;i++){
if(ans[i]==1){
putchar('R');
}
else if(ans[i]==2){
putchar('L');
}
else{
putchar('B');
}
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
[NOI2023] 方格染色
题面
因为求的是总数量，所以哪条线先染色哪条线后染色是没有区别的。我们可以先处理横线和竖线，这个部分都是矩形，可以使用扫描线处理。
对于斜线，我们发现最多有 \(5\) 条，且方向只有一个，可以直接枚举每条直线得到已经计算过的点有哪些。注意，如果两条斜线有交集，为了防止重复计算，只计算两条斜线的并即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10;
int n,m,q,cnt1,cnt2;
struct Node{
int stx,sty,edx,edy;
}a[N],b[10];
struct node{
int xl,xr,y,opt;
}seg[N<<1];
int x[N<<1];
bool cmp(node x,node y){
return x.y<y.y;
}
bool cmp2(Node x,Node y){
return x.stx==y.stx?x.sty<y.sty:x.stx<y.stx;
}
namespace Seg_Tree{
int ans[N<<2],tag[N<<2];
int ls(int p){
return p<<1;
}
int rs(int p){
return p<<1|1;
}
void push_up(int p,int l,int r){
if(tag[p]){
ans[p]=x[r+1]-x[l];
}
else{
ans[p]=ans[ls(p)]+ans[rs(p)];
}
}
void update(int p,int l,int r,int q_l,int q_r,int val){
if(x[r+1]<=q_l||q_r<=x[l]){
return;
}
if(q_l<=x[l]&&x[r+1]<=q_r){
tag[p]+=val;
push_up(p,l,r);
return;
}
int mid=(l+r)>>1;
update(ls(p),l,mid,q_l,q_r,val);
update(rs(p),mid+1,r,q_l,q_r,val);
push_up(p,l,r);
}
}
void solve(){
read(n),read(m),read(q);
for(int i=1;i<=q;i++){
int opt,stx,sty,edx,edy;
read(opt),read(stx),read(sty),read(edx),read(edy);
if(opt==1||opt==2){
edx++;
edy++;
a[++cnt1].stx=stx;
a[cnt1].sty=sty;
a[cnt1].edx=edx;
a[cnt1].edy=edy;
}
else{
b[++cnt2].stx=stx;
b[cnt2].sty=sty;
b[cnt2].edx=edx;
b[cnt2].edy=edy;
}
}
for(int i=1;i<=cnt1;i++){
x[i*2-1]=a[i].stx;
x[i*2]=a[i].edx;
seg[i*2-1]=node{a[i].stx,a[i].edx,a[i].sty,1};
seg[i*2]=node{a[i].stx,a[i].edx,a[i].edy,-1};
a[i].edx--;
a[i].edy--;
}
n=cnt1*2;
sort(seg+1,seg+n+1,cmp);
sort(x+1,x+n+1);
m=unique(x+1,x+n+1)-x-1;
int ans=0;
for(int i=1;i<n;i++){
Seg_Tree::update(1,1,m-1,seg[i].xl,seg[i].xr,seg[i].opt);
ans+=Seg_Tree::ans[1]*(seg[i+1].y-seg[i].y);
}
sort(b+1,b+cnt2+1,cmp2);
for(int i=1;i<=cnt2;i++){
if(b[i].stx==-1){
continue;
}
for(int j=i+1;j<=cnt2;j++){
if(b[i].stx-b[i].sty==b[j].stx-b[j].sty){
if(b[i].edx>=b[j].edx){
b[j].stx=b[j].sty=b[j].edx=b[j].edy=-1;
}
else{
b[j].stx=b[i].edx+1;
b[j].sty=b[i].edy+1;
}
}
}
}
for(int i=1;i<=cnt2;i++){
if(b[i].stx==-1){
continue;
}
ans+=(b[i].edx-b[i].stx+1);
map<pii,int>vis;
for(int j=1;j<=cnt1;j++){
if(a[j].stx==a[j].edx){
if(a[j].stx>=b[i].stx&&a[j].stx<=b[i].edx){
int pos=b[i].sty+(a[j].stx-b[i].stx);
if(pos>=a[j].sty&&pos<=a[j].edy){
if(!vis.count(mp(a[j].stx,pos))){
vis[mp(a[j].stx,pos)]=1;
ans--;
}
}
}
}
else if(a[j].sty==a[j].edy){
if(a[j].sty>=b[i].sty&&a[j].sty<=b[i].edy){
int pos=b[i].stx+(a[j].sty-b[i].sty);
if(pos>=a[j].stx&&pos<=a[j].edx){
if(!vis.count(mp(pos,a[j].sty))){
vis[mp(pos,a[j].sty)]=1;
ans--;
}
}
}
}
}
}
write_endl(ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
#endif
int t;
read(t);
t=1;
while(t--){
solve();
}
return 0;
}
[NOI2023] 贸易
题面
没有横叉边，对于一条路径 \((u,v)\) 是可以直接拆分成 \((u,lca(u,v))\) 和 \((lca(u,v),v)\) 两条路径。
\((u,lca(u,v))\) 这条路径一定是走的第一条路径，因为第二类边均为前向边，要走必然形成环，不是简单路径，不会更优。
\((lca(u,v),v)\) 这条路径，因为有了前向边的参与，通过带有前向边的环，可以实现由祖先到儿子。令 \(f_{u,i}\) 表示从 \(u\) 的深度为 \(i\) 的祖先到它的最短路，一条前向边 \((u,v)\) 可以影响所有原来有路径 \(v\rightarrow y\rightarrow x\rightarrow u\) 的祖孙对 \((x,y)\) 的 \(f_{y,dep_x}\)。然后便可以像floyd求最短路一样求出每个点的祖先到它的最短路。
这题中的 \(dep\) 和 \(siz\) 都是显然易得的，\(dep_u=\log u,siz_u=2^{n-dep_u}-1\)，求一对点 \((v,u)\) 的答案，可以分类讨论。如果 \(v\) 在 \(u\) 子树内，可以直接计算 \(u\) 子树内点到 \(u\) 的距离和。如果 \(v\) 在子树外，可以枚举两个点的 \(lca\)，如果 \(lca\) 能到 \(u\)，那么对于所有 \(lca(u,v)=lca\) 的点的也是可以直接一起统计的。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=18,mod=998244353,M=(1<<N)+10,inf=1e18;
int n,m,a[M],f[M][N],dis[M],sum[M],siz[M],ans;
//sum 表示 u 子树内的点到 u 的距离和，siz 表示子树大小，dis 表示根到 u 的距离
void solve(){
read(n),read(m);
for(int i=2;i<(1<<n);i++){
read(a[i]);
dis[i]=dis[i>>1]+a[i];
}
for(int i=1;i<(1<<n);i++){
siz[i]=(1<<(n-__lg(i)))-1;
}
for(int i=(1<<n)-1;i>1;i--){
sum[i>>1]+=(sum[i]+siz[i]*a[i]);
//子树内所有节点到父节点的距离为子树内的点到子树根节点的距离加上子树内点经过根节点到父亲边的距离和
}
memset(f,0x3f,sizeof(f));
while(m--){
int u,v,w;
read(u),read(v),read(w);
for(int y=v;y>u;y>>=1){
for(int x=y>>1;x>=u;x>>=1){
f[y][__lg(x)]=min(f[y][__lg(x)],w+dis[v]-dis[y]+dis[x]-dis[u]);
}
}
}
for(int u=1;u<(1<<n);u++){
for(int i=__lg(u)-1,v=u>>1;v;--i,v>>=1){
for(int j=i-1;j>=0;j--){
f[u][j]=min(f[u][j],f[u][i]+f[v][j]);
}
}
}
for(int u=(1<<n)-1;u;u--){
ans=(ans+sum[u])%mod;
for(int i=__lg(u)-1,v=u;v>1;i--,v>>=1){//枚举的 lca 是 u 的深度为 i 的祖先，v表示 u 的深度为 i+1的祖先，v^1 表示 v 的兄弟
if(f[u][i]<inf){
ans=(ans+f[u][i]*(siz[v^1]+1)%mod+(sum[v^1]+siz[v^1]*a[v^1])%mod)%mod;//计算 v 的兄弟子树内的点和 v 父亲到 u 的距离和
}
}
}
write_endl(ans);
}
signed main(){
// freopen("trade.in","r",stdin);
// freopen("trade.out","w",stdout);
int t=1;
while(t--){
solve();
}
return 0;
}