hdu 5469 Antonidas 樹形dp+暴力 ★

Antonidas

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 1163    Accepted Submission(s): 334

Problem Description Given a tree with  N  vertices and  N−1  edges. Each vertex has a single letter  Ci . Given a string  S , you are to choose two vertices A and B, and make sure the letters catenated on the shortest path from A to B is exactly S. Now, would you mind telling me whether the path exists?

Input The first line is an integer T, the number of test cases.

For each case, the first line is an integer  N . Following  N−1  lines contains two integers a and b, meaning there is an edge connect vertex a and vertex b.

Next line contains a string C, the length of C is exactly  N . String C represents the letter on each vertex.

Next line contains a string S.

1≤T≤200 ,  1≤N≤104 ,  1≤a,b≤N ,  a≠b ,  |C|=N ,  1≤|S|≤104 . String C and S both only contain lower case letters.  

Output First, please output "Case #k: ", k is the number of test case. See sample output for more detail.

If the path exists, please output “Find”. Otherwise, please output “Impossible”.  

Sample Input

2

7
1 2
2 3
2 4
1 5
5 6
6 7
abcdefg
dbaefg

5
1 2
2 3
2 4
4 5
abcxy
yxbac
        

Sample Output

Case #1: Find
Case #2: Impossible
        

Source 2015 ACM/ICPC Asia Regional Shanghai Online  

Recommend hujie   |   We have carefully selected several similar problems for you:   5932  5931  5930  5929  5928   

Statistic |  Submit |  Discuss |  Note

  題意：給出一棵樹，每個結點對應一個字元。現在給出一個字元串。問樹上有無某兩點的最短路能比對該字元串。

解法：因為長度為1e4，結點數為1e4。加上一些剪枝(比如從樹上某個結點往下比對，但是往下最多走d步，字元串剩餘超過d個字元，直接剪枝即可)，完全可以用暴力比對算法。

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define for0(a, n) for (int (a) = 0; (a) < (n); (a)++)
#define for1(a, n) for (int (a) = 1; (a) <= (n); (a)++)
#define mes(a,x,s)  memset(a,x,(s)*sizeof a[0])
#define mem(a,x)  memset(a,x,sizeof a)
#define ysk(x)  (1<<(x))
typedef long long ll;
typedef pair<int, int> pii;
const int INF =0x3f3f3f3f;
const int maxn=10000    ;
int nedge,fir[maxn+10],lenS;
int n,F[maxn+10],dp[maxn+10];
char C[maxn+10],S[maxn+10];
bool vis[maxn+10];
struct Edge
{
    int to,nex;
} e[2*maxn+10];

inline void add_edge(int x,int y)
{
    e[nedge].to=y;
    e[nedge].nex=fir[x];

    fir[x]=nedge++;
}

void dfs(int x,int fa)
{
    F[x]=fa;
    dp[x]=0;
    for(int i=fir[x];~i;i=e[i].nex)
    {
        int y=e[i].to;if(y==fa) continue;
        dfs(y,x);
        dp[x]=max(dp[x],dp[y]);
    }
    dp[x]++;
}


bool find(int x,int p)
{
   if(p==lenS)  return true;
   for(int i=fir[x];~i;i=e[i].nex)
   {
       int y=e[i].to;if(y==F[x]||vis[y]) continue;

       if(C[y]==S[p+1]&&dp[y]>=lenS-p)
       {

           vis[y]=1;
          if(find(y,p+1)) return true;
       }

   }
   int fa=F[x];
   if(~fa&&!vis[fa]&&C[fa]==S[p+1])
   {
       vis[fa]=1;
       if(find(fa,p+1)) return true;
   }
   return false;


}
bool solve()
{
    for1(i,n)
    {
       if(C[i]==S[1])
       {
           mes(vis,0,n+1);
           vis[i]=1;
           if( find(i,1) )  return true;
       }
    }
    return false;
}
int main()
{
   int T,x,y,kase=0;scanf("%d",&T);
   while(T--)
   {
       scanf("%d",&n);mes(fir,-1,n+1);
       nedge=0;
       for1(i,n-1)
       {
           scanf("%d%d",&x,&y);
           add_edge(x,y);
           add_edge(y,x);
       }
       dfs(1,-1);
       scanf("%s",C+1);
       scanf("%s",S+1);
       lenS=strlen(S+1);
       printf("Case #%d: ",++kase);
       puts(solve()?"Find":"Impossible");

   }
   return 0;
}