网站与域名的区别,中国展厅设计公司排名,网站策划包括什么,怎么查域名是否被注册线图 如图#xff0c;每个L(L(T))上的点对应T上的一条三点链 在连接L(L(T))上两点#xff0c;当且仅当两点代表的三点链在T上有共边#xff0c;且边权为 共边边权*2非共边1边权非共边2边权 在L(L(T))上从点u走到点v#xff0c;等价于u代表的三点链在T上删掉自己的一条边每个L(L(T))上的点对应T上的一条三点链 在连接L(L(T))上两点当且仅当两点代表的三点链在T上有共边且边权为 共边边权*2非共边1边权非共边2边权 在L(L(T))上从点u走到点v等价于u代表的三点链在T上删掉自己的一条边然后在剩下来的两个点上选一个点接一条边转化为v代表的三点链代价为 不动边边权*2删边边权接边边权 先考虑两个三点链在树上的最短路。此处不赘述大体上的分类讨论如图 拓展到求任意两三点链的最短路径总和可以用树形DP实现考虑如何做到不重不漏 1.首先每对不相交三点链的贡献可以拆成两部分树上最短路径的贡献三点链的贡献。三点链的贡献只与树上最短路径连接的是三点链的中点还是端点有关与具体选择什么样的最短路径无关 而一条边作为树上最短路径的一部分时贡献永远是自身边权*4。 所以我们可以对每条边分别讨论它 作为三点链的一部分的贡献 和 作为树上最短路的一部分的贡献再把这两部分的贡献加起来。 2.再考虑相交的三点链对。 对于X型我们对每条边讨论它为四边中第1小、第2小、第3小、第4小边时自身的贡献再把这些贡献加起来。 对于Y型边(u,v)(ufa[v]u的度数为d)作为Y型的共边出现的情况有(d−1)(d−2)/2(d-1)(d-2)/2(d−1)(d−2)/2种作为非共边出现的情况有(d−1)(d−2)(d-1)(d-2)(d−1)(d−2)种我们在扫到这条边时直接给答案加上(d−1)(d−2)/2×4×边权(d-1)(d-2)/2\times4\times边权(d−1)(d−2)/2×4×边权即可。 对于Z型我们在共边处统计出整个Z型的贡献。
ps:为保证不重不漏地考虑到所有的三点链我们在DP到树节点u时就只考虑以u为中点的三点链
#includeiostream
#includecstdio
#includealgorithm
#define int long long
using namespace std;
const int N5e55;
const int mod998244353;
int read(){int x0,f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){xx*10ch-0;chgetchar();}return x*f;
}
int add(int a,int b){return (ab)%mod;}
int dec(int a,int b){return ((a-b)%modmod)%mod;}
void Add(int a,int b){aadd(a,b);}
struct Edge{int v,w,nxt;
}e[N1];
int n,d[N],head[N],cnt0,ans;
int f[N],g[N];
//f[i]i子树内三点链的个数
//g[i]i子树外三点链的个数
int addedge(int u,int v,int w){e[cnt].vv;e[cnt].ww;e[cnt].nxthead[u];head[u]cnt;
}
void dfs(int u,int ff){f[u]1ll*d[u]*(d[u]-1)/2%mod;for(int ihead[u];i;ie[i].nxt){if(e[i].v!ff){dfs(e[i].v,u);Add(f[u],f[e[i].v]);}}
}
int to[N],val[N],Sw[N];
int su[N],sv[N];
int pre[N],suf[N];
bool cmp(int a,int b){return val[a]val[b];
}
void work(int u,int ff){for(int ihead[u];i;ie[i].nxt){int ve[i].v;if(vff) continue;work(v,u);}int tot0;for(int ihead[u];i;ie[i].nxt){int ve[i].v;to[tot]v;val[v]e[i].w; Add(Sw[u],e[i].w);su[v]vff?f[u]:g[v];sv[v]vff?g[u]:f[v];}sort(to1,totot1,cmp);pre[0]suf[tot1]0; for(int i1;itot;i) pre[i]add(pre[i-1],sv[to[i]]);for(int itot;i;i--) suf[i]add(suf[i1],sv[to[i]]);for(int i1;itot;i){int vto[i],dud[u],dvd[v],wval[v];//处理这条边为相交的三点链做的贡献 Add(ans,1ll*(tot-i)*(tot-i-1)*(tot-i-2)/6*9%mod*w%mod);//以u为中心的X型当前边为第1小边 Add(ans,1ll*(i-1)*(tot-i)*(tot-i-1)/2*7%mod*w%mod);//以u为中心的X型当前边为第2小边 Add(ans,1ll*(i-1)*(i-2)/2*(tot-i)*5%mod*w%mod);//以u为中心的X型当前边为第3小边 Add(ans,1ll*(i-1)*(i-2)*(i-3)/6*3%mod*w%mod);//以u为中心的X型当前边为第4小边 Add(ans,1ll*(tot-1)*(tot-2)/2*4%mod*w%mod);//以u为中心的Y型if(v!ff) Add(ans,1ll*(du-1)*(dv-1)*2%mod*w%modadd(1ll*(Sw[u]-w)*(dv-1)%mod,1ll*(Sw[v]-w)*(du-1)%mod));//以u为中心的Z型 //处理这条边为不相交的三点链做的贡献 if(v!ff) Add(ans,1ll*(sv[v]-(dv-1))*(su[v]-(du-1))*4%mod*w%mod);//这条边在树上最短路径中注意if Add(ans,1ll*dec(su[v],1ll*du*(du-1)/2%mod)*(tot-2)%mod*w%mod); Add(ans,1ll*dec(su[v],pre[i-1]1ll*du*(du-1)/2%mod)*(tot-i-1)%mod*2*w%mod);Add(ans,1ll*dec(su[v],suf[i1]1ll*du*(du-1)/2%mod)*(tot-i)%mod*2*w%mod);//树上最短路径连中点uAdd(ans,(1ll*(tot-1)*3*w%mod1ll*(Sw[u]-w))*(sv[v]-(dv-1))%mod);//树上最短路径连端点v }
}
signed main(){nread();for(int i1;in;i){int uread(),vread(),wread();addedge(u,v,w);addedge(v,u,w);d[u];d[v];}dfs(1,0);for(int i1;in;i) g[i]f[1]-f[i];work(1,0);coutdec(ans,0)endl;return 0;
}
