題目鏈接：點擊查看

題目大意：給出 n 個點組成的一棵樹，每個節點都有一個權值，現在規定權值相同的節點之間，簡單路徑的邊數為 x ，求 x * x 的最大值

題目分析：真的很巧，上周剛學的虛樹，讀完這個題的第一反應就是可以用虛樹簡化題目，其實完全可以用樹形dp跑一遍dfs出來，可奈何我dp不好，就只能用虛樹來做了

題目中有兩個點可以單獨考慮，首先是權值相同的點，這個就可以用虛樹將權值相同的點都拎出來，然后是簡單路徑的邊數最大，這個對應著樹的直徑，所以直接虛樹配合樹的直徑寫一個dfs，直接維護最大值就好了

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;vector<int>pos[N];bool cmp(int x,int y);struct virtual_tree {//原樹部分 struct{int to,next;}edge[N<<1];int head[N],cnt,deep[N],dp[N][20],limit;//樹上倍增int L[N],R[N],dfn;//dfs序 void addedge(int u,int v){edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;}void dfs(int u,int fa,int dep){L[u]=++dfn;deep[u]=dep;dp[u][0]=fa;for(int i=1;i<=limit;i++)dp[u][i]=dp[dp[u][i-1]][i-1];for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(v!=fa)dfs(v,u,dep+1);}R[u]=dfn;}int LCA(int x,int y){if(deep[x]<deep[y])swap(x,y);for(int i=limit;i>=0;i--)if(deep[x]-deep[y]>=(1<<i))x=dp[x][i];if(x==y)return x;for(int i=limit;i>=0;i--)if(dp[x][i]!=dp[y][i]){x=dp[x][i];y=dp[y][i];}return dp[x][0];}void init(int n){memset(head,-1,sizeof(head));cnt=dfn=0;limit=log2(n)+1;for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);addedge(u,v);addedge(v,u);}}//虛樹部分 vector<int>node[N];vector<int>ver;int Stack[N];void build(){sort(ver.begin(),ver.end(),cmp);int sz=ver.size()-1;for(int i=0;i<sz;i++)ver.push_back(LCA(ver[i],ver[i+1]));sort(ver.begin(),ver.end(),cmp);ver.erase(unique(ver.begin(),ver.end()),ver.end());int top=0;Stack[++top]=ver[0];for(int i=1;i<ver.size();i++){while(top&&R[Stack[top]]<L[ver[i]])top--;if(top)node[Stack[top]].push_back(ver[i]);Stack[++top]=ver[i];}}void clear(){for(int i=0;i<ver.size();i++)node[ver[i]].clear();ver.clear();}int d[N],ans;void dfs(int u,int fa){d[u]=0;for(auto v:node[u]){if(v==fa)continue;dfs(v,u);int w=deep[v]-deep[u];ans=max(ans,d[v]+d[u]+w);d[u]=max(d[u],d[v]+w);}}LL solve(int val){ver=pos[val];build();//建虛樹 ans=0;dfs(ver.front(),-1);//樹形dp求樹的直徑 clear();//初始化 return ans;} }tree;bool cmp(int x,int y) {return tree.L[x]<tree.L[y]; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++){int num; scanf("%d",&num);pos[num].push_back(i);}tree.init(n);tree.dfs(1,0,0);LL mmax=0;for(int i=1;i<=n;i++)if(pos[i].size())mmax=max(mmax,tree.solve(i));printf("%lld\n",mmax*mmax);return 0; }

?

總結

以上是生活随笔為你收集整理的牛客 - 王国(虚树+树的直径)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。