网站设计中的div是什么,企业网站策划书制作, 百度一下,旅游网网站建设正题
题目链接:https://www.luogu.com.cn/problem/P3346 题目大意
一棵树#xff0c;求树上所有路径构成的字符串有多少种。#xff08;叶子不超过303030个#xff09; 解题思路
如果是根节点到一些节点的路径的话很好做#xff0c;直接建广义SAMSAMSAM即可#xff0c;…正题
题目链接:https://www.luogu.com.cn/problem/P3346 题目大意
一棵树求树上所有路径构成的字符串有多少种。叶子不超过303030个 解题思路
如果是根节点到一些节点的路径的话很好做直接建广义SAMSAMSAM即可但是因为路径会拐弯所以我们考虑如何统计拐弯的路径。
不难发现如果选择另一个叶子作为根那么就能让某些拐弯的路径变直在每个叶子节点处都跑一遍建立广义SAMSAMSAM即可。
时间复杂度O(30n)O(30n)O(30n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e510,M3e610;;
struct node{ll to,next;
}a[N*2];
ll n,m,tot,ans,w[N],ls[N],in[N];
ll cnt,len[M],fa[M],ch[M][10];
ll Ins(ll c,ll p){if(ch[p][c]){ll qch[p][c];if(len[p]1len[q])return q;else{ll nqcnt;len[nq]len[p]1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]fa[q];fa[q]nq;for(;pch[p][c]q;pfa[p])ch[p][c]nq;return nq;}}ll npcnt;len[np]len[p]1;for(;p!ch[p][c];pfa[p])ch[p][c]np;if(!p)fa[np]1;else{ll qch[p][c];if(len[p]1len[q])fa[np]q;else{ll nqcnt;len[nq]len[p]1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]fa[q];fa[np]fa[q]nq;for(;pch[p][c]q;pfa[p])ch[p][c]nq;}}return np;
}
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;in[y];return;
}
void dfs(ll x,ll fa,ll last){ll tmpIns(w[x],last);for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;dfs(y,x,tmp);}return;
}
int main()
{scanf(%lld%lld,n,m);cnt1;for(ll i1;in;i)scanf(%lld,w[i]);for(ll i1;in;i){ll x,y;scanf(%lld%lld,x,y);addl(x,y);addl(y,x);}for(ll i1;in;i)if(in[i]1)dfs(i,0,1);for(ll i1;icnt;i)anslen[i]-len[fa[i]];printf(%lld,ans);
}
